题意：定义一个无穷项的多项式f(x)f(x)f(x)，初始各项系数都为0，现在有几种操作
-
将xLx^LxL到xRx^RxR这些项的系数乘上某个定值v
-
将xLx^LxL到xRx^RxR这些项的系数加上某个定值v
-
将xLx^LxL到xRx^RxR这些项乘上x变量
-
将某个定值v代入多项式F(x)，并输出代入后多项式的值，之后多项式还原为代入前的状况
其中第四种操作不会出现超过10次。
N≤105，0≤L≤R≤105，0≤v≤109N\le10^5，0\le L\le R \le10^5，0 \le v\le10^9N≤105，0≤L≤R≤105，0≤v≤109
思路：
由于第四个操作不会出现超过101010次因此如果能快速维护各项系数可以O(n)O(n)O(n)遍历。
头两个操作是基操我们跳过吧qwqqwqqwq
主要看第三个操作，想象我们对x0x^0x0~x100001x^{100001}x100001这些项的系数用一棵平衡树来维护，这样操作三相当于将xrx^rxr的系数加到xr+1x^{r+1}xr+1上面，然后删掉这个xrx^rxr，然后把xlx^lxl ~xr−1x^{r-1}xr−1对应次数全部加111，然后插入一个新的系数为000的xlx^lxl。
于是这道题就做完了。
代码：
#include<bits/stdc++.h>#define ri register int#define fi first#define se secondusing namespace std;inline int read(){ #define gc getchar int ans=0; char ch=gc(); while(!isdigit(ch))ch=gc(); while(isdigit(ch))ans=((ans<<2)+ans<<1)+(ch^48),ch=gc(); return ans; #undef gc}typedef long long ll;typedef pair<int,int> pii;const int N=2e5+5,mod=20130426;inline int add(const int&a,const int&b){return a+b>=mod?a+b-mod:a+b;}inline int mul(const int&a,const int&b){return (ll)a*b%mod;}int pw[N],ans,n=100001;namespace bst{ #define lc (son[p][0]) #define rc (son[p][1]) int val[N],coe[N],siz[N],det[N],ad[N],ml[N],son[N][2],rd[N],rt=0,tot=0; inline int get(int v){return val[++tot]=v,siz[tot]=ml[tot]=1,rd[tot]=rand(),tot;} inline void pushup(int p){siz[p]=siz[lc]+1+siz[rc];} inline void pushval(int p,int v){if(!p)return;val[p]+=v,det[p]+=v;} inline void pushnow(int p,int v1,int v2){if(!p)return;coe[p]=add(mul(coe[p],v1),v2),ad[p]=add(mul(ad[p],v1),v2),ml[p]=mul(ml[p],v1);} inline void pushdown(int p){ if(det[p]){ if(lc)pushval(lc,det[p]); if(rc)pushval(rc,det[p]); det[p]=0; } if(ad[p]||ml[p]!=1){ if(lc)pushnow(lc,ml[p],ad[p]); if(rc)pushnow(rc,ml[p],ad[p]); ml[p]=1,ad[p]=0; } } inline int merge(int a,int b){ if(!a||!b)return a+b; pushdown(a),pushdown(b); if(rd[a]>rd[b])return son[a][1]=merge(son[a][1],b),pushup(a),a; return son[b][0]=merge(a,son[b][0]),pushup(b),b; } inline pii split(int p,int k){ if(!p)return pii(0,0); pii tmp; pushdown(p); if(siz[lc]>=k)return tmp=split(lc,k),lc=tmp.se,pushup(p),pii(tmp.fi,p); return tmp=split(rc,k-siz[lc]-1),rc=tmp.fi,pushup(p),pii(p,tmp.se); } inline void insert(int id,int v){ pii x=split(rt,id-1); rt=merge(x.fi,merge(get(v),x.se)); } inline void build(int&p,int l,int r){ if(l>r)return; int mid=l+r>>1; if(l==r){p=get(l-1);return;} p=get(mid-1),build(lc,l,mid-1),build(rc,mid+1,r),pushup(p); } inline void update(int l,int r,int v1,int v2){ pii x=split(rt,l-1),y=split(x.se,r-l+1); pushnow(y.fi,v1,v2),rt=merge(x.fi,merge(y.fi,y.se)); } inline void modify(int l,int r){ pii x=split(rt,l-1),y=split(x.se,r-l+2),z=split(y.fi,r-l),t=split(z.se,1); coe[t.se]=add(coe[t.se],coe[t.fi]),pushval(z.fi,1),rt=merge(x.fi,merge(merge(z.fi,t.se),y.se)); insert(l,l-1); } inline void query(int p){ ans=add(ans,mul(pw[val[p]],coe[p])); pushdown(p); if(lc)query(lc); if(rc)query(rc); } #undef lc #undef rc}char s[5];int main(){ srand(time(NULL)); bst::build(bst::rt,1,n+1); for(ri tt=read(),l,r,v;tt;--tt){ scanf("%s",s); if(s[0]=='a'){ l=read()+1,r=read()+1,v=read()%mod; bst::update(l,r,1,v); } if(s[0]=='m'&&strlen(s)==3){ l=read()+1,r=read()+1,v=read()%mod; bst::update(l,r,v,0); } if(s[0]=='m'&&strlen(s)==4){ l=read()+1,r=read()+1; bst::modify(l,r); } if(s[0]=='q'){ v=read(); pw[0]=1; ans=0; for(ri i=1;i<=n;++i)pw[i]=mul(pw[i-1],v); bst::query(bst::rt); cout<<ans<<'\n'; } } return 0;}
