---恢复内容开始---
又是一道裸数据结构题。
之前受序列操作的蛋疼写法影响，只用一个tag，不知道怎么记，之后看了下别人的，终于领悟要用两个tag，一个add,一个mul，维护相当简单，想清楚就行。
简单说下解法。
add mul就是一般的将[L,R]split出来然后打tag.
mulx：我将[L,R+1]split出来，然后这一段split成l:[L,R-1],mid:[R,R],r[R+1,R+1]，然后把mid的系数加到r上，把mid的系数赋为0，然后merge(mid,l,r);这里注意如果L==R将会出现问题，于是这里我特判了一下。
还是就是见乘就得加long long.....
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstdlib> 5 #include<cstring> 6 using namespace std; 7 const int Maxn=100000+10,Mod=20130426,MaxR=100001; 8 int _a[Maxn],cnt; 9 inline void fadd(int&a,int b){ 10 a+=b;if(a>Mod)a-=Mod; 11 } 12 struct node{ 13 int v,sz,add,mul;//itself isn't in it 14 node*ch[2]; 15 node(){ 16 sz=v=add=0;mul=1; 17 } 18 inline void maintain(){ 19 sz=ch[0]->sz+ch[1]->sz+1; 20 } 21 inline int cmp(int k){ 22 if(ch[0]->sz+1==k)return -1; 23 return k>ch[0]->sz+1; 24 } 25 inline void AddTag(int Add,int Mul){ 26 v=(long long)v*Mul%Mod; 27 fadd(v,Add); 28 mul=(long long)mul*Mul%Mod;//注意long long 29 add=(long long)add*Mul%Mod;//注意long long 30 fadd(add,Add); 31 } 32 inline void down(){ 33 ch[0]->AddTag(add,mul); 34 ch[1]->AddTag(add,mul); 35 add=0;mul=1; 36 } 37 }da[Maxn],*root,*null;int tot; 38 inline void rotate(node*&o,int d){ 39 node*t=o->ch[d]; 40 o->ch[d]=t->ch[d^1]; 41 t->ch[d^1]=o; 42 o->maintain(); 43 (o=t)->maintain(); 44 } 45 void splay(node*&o,int k){ 46 o->down(); 47 int d=o->cmp(k); 48 if(d==-1)return; 49 if(d)k-=o->ch[0]->sz+1; 50 node*&p=o->ch[d]; 51 p->down(); 52 int d2=p->cmp(k); 53 if(d2!=-1){ 54 if(d2)k-=p->ch[0]->sz+1; 55 splay(p->ch[d2],k); 56 if(d2!=d)rotate(p,d2); 57 else rotate(o,d); 58 } 59 rotate(o,d); 60 } 61 void build(node*&o,int l,int r){ 62 if(l>r){ 63 o=null; 64 return; 65 } 66 int mid=(l+r)>>1; 67 o=da+ ++tot; 68 build(o->ch[0],l,mid-1); 69 build(o->ch[1],mid+1,r); 70 o->maintain(); 71 } 72 void print(node*o){ 73 if(o==null)return; 74 o->down(); 75 print(o->ch[0]); 76 ++cnt; 77 if(cnt>=2 && cnt<=MaxR+2)_a[cnt-2]=o->v; 78 // printf("%d ",o->v); 79 print(o->ch[1]); 80 } 81 inline int calc(int x,const int*a){ 82 int ret=a[MaxR]; 83 for(int i=MaxR;i>=0;i--){ 84 ret=(long long)ret*x%Mod; 85 fadd(ret,a[i]); 86 } 87 return ret; 88 } 89 inline void split(node*o,int k,node*&l,node*&r){ 90 splay(o,k); 91 r=o->ch[1]; 92 (l=o)->ch[1]=null; 93 l->maintain(); 94 } 95 inline node*merge(node*l,node*r){ 96 splay(l,l->sz); 97 l->ch[1]=r; 98 l->maintain(); 99 return l; 100 } 101 int get_tp(char *opt){ 102 if(opt[0]=='a')return 1; 103 if(opt[0]=='m')return opt[3]?3:2; 104 return 4; 105 } 106 int main(){ 107 freopen("polynomial.in","r",stdin); 108 freopen("polynomial.out","w",stdout); 109 110 int tp,L,R,V,n; 111 null=da; 112 null->ch[0]=null->ch[1]=null; 113 build(root,1,MaxR+2); 114 node*o,*l,*r,*mid; 115 char opt[10]={0}; 116 for(scanf("%d ",&n);n--;){ 117 scanf("%s",opt); 118 tp=get_tp(opt); 119 if(tp<=2){ 120 scanf("%d%d%d",&L,&R,&V);V%=Mod; 121 split(root,L+1,l,o); 122 split(o,R-L+1,mid,r); 123 if(tp==1)mid->AddTag(V,1); 124 else mid->AddTag(0,V); 125 root=merge(merge(l,mid),r); 126 } 127 else if(tp==3){ 128 scanf("%d%d",&L,&R); 129 split(root,L+1,l,o); 130 split(o,R-L+2,mid,r); 131 if(R==L){//这里必须特判 132 splay(mid,1); 133 mid->down(); 134 mid->ch[1]->down(); 135 fadd(mid->ch[1]->v,mid->v); 136 mid->v=0; 137 }else{ 138 node*_o,*_l,*_r,*_mid; 139 split(mid,mid->sz-2,_l,_o); 140 split(_o,1,_mid,_r); 141 _mid->down(); 142 _r->down(); 143 fadd(_r->v,_mid->v); 144 _mid->v=0; 145 mid=merge(merge(_mid,_l),_r); 146 } 147 root=merge(merge(l,mid),r); 148 } 149 else { 150 scanf("%d",&V);V%=Mod; 151 cnt=0; 152 print(root); 153 printf("%d ",calc(V,_a)); 154 } 155 } 156 157 return 0; 158 }