SCOI2013 day1 多项式的运算(polynomial)

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 typedef long long ll;
  7 #define inc(a,b) a+=b,a=a>=MOD?a-MOD:a
  8 const int MOD=20130426;
  9 const int MAXP=200010;
 10 
 11 struct _Node
 12 {
 13     int v,add,mul,size;
 14     _Node *s[2],*fa;
 15 }pool[MAXP],*stk[MAXP],root,null;
 16 
 17 int idx,stat[MAXP];
 18 
 19 _Node* new_Node(_Node *fa)
 20 {
 21     _Node *ret=pool+(idx++);
 22     ret->v=ret->add=0;
 23     ret->size=ret->mul=1;
 24     ret->s[0]=ret->s[1]=&null;
 25     ret->fa=fa;
 26     return ret;
 27 }
 28 void _update(_Node *now)
 29 {
 30     now->size=now->s[0]->size+now->s[1]->size+1;
 31 }
 32 void init()
 33 {
 34     root.s[0]=new_Node(&root);
 35     root.s[0]->s[1]=new_Node(root.s[0]);
 36     _Node *lst=root.s[0]->s[1];
 37     for (int i=100001;i>=1;--i)
 38     {
 39         lst->s[0]=new_Node(lst);
 40         lst->s[0]->size=i;
 41         lst=lst->s[0];
 42     }
 43     _update(root.s[0]->s[1]);
 44     _update(root.s[0]);
 45 }
 46 void _push_down(_Node *now)
 47 {
 48     if (now->mul!=1)
 49     {
 50         now->s[0]->mul=(ll)now->s[0]->mul*now->mul%MOD;
 51         now->s[1]->mul=(ll)now->s[1]->mul*now->mul%MOD;
 52         now->s[0]->add=(ll)now->s[0]->add*now->mul%MOD;
 53         now->s[1]->add=(ll)now->s[1]->add*now->mul%MOD;
 54         now->s[0]->v=(ll)now->s[0]->v*now->mul%MOD;
 55         now->s[1]->v=(ll)now->s[1]->v*now->mul%MOD;
 56         now->mul=1;
 57     }
 58     if (now->add)
 59     {
 60         inc(now->s[0]->add,now->add);
 61         inc(now->s[0]->v,now->add);
 62         inc(now->s[1]->add,now->add);
 63         inc(now->s[1]->v,now->add);
 64         now->add=0;
 65     }
 66 }
 67 void _rot(_Node *now,int d)
 68 {
 69     _Node *s=now->s[d],*fa=now->fa;
 70     (now->s[d]=s->s[!d])->fa=now;
 71     (s->s[!d]=now)->fa=s;
 72     (fa->s[fa->s[1]==now]=s)->fa=fa;
 73     _update(now);
 74 }
 75 void _splay(_Node *now,_Node *&aim)
 76 {
 77     _Node *&p=now->fa,*g;
 78     int dp,dg;
 79     while (p!=aim && now!=aim)
 80     {
 81         g=p->fa;
 82         if ((dp=p->s[1]==now) == (dg=g->s[1]==p))
 83             _rot(g,dg),_rot(p,dp);
 84         else _rot(p,dp),_rot(g,dg);
 85     }
 86     if (now!=aim) _rot(aim,aim->s[1]==now);
 87     _update(now);
 88 }
 89 _Node* select(int k)
 90 {
 91     _Node *now=root.s[0];
 92     while (1)
 93     {
 94         _push_down(now);
 95         if (now->s[0]->size==k) return now;
 96         if (now->s[0]->size<k) k-=now->s[0]->size+1,now=now->s[1];
 97         else now=now->s[0];
 98     }
 99 }
100 void mulx(int a,int b)
101 {
102     _splay(select(b-1),root.s[0]);
103     _splay(select(b+1),root.s[0]->s[1]);
104     _Node *now=root.s[0]->s[1];
105     _push_down(now->s[0]);
106     _Node tmp=*(now->s[0]);
107     now->s[0]=&null;
108     inc(now->v,tmp.v);
109     _splay(select(a-1),root.s[0]);
110     _splay(select(a),root.s[0]->s[1]);
111     _Node *&cur=root.s[0]->s[1]->s[0];
112     cur=new_Node(root.s[0]->s[1]);
113     _update(root.s[0]->s[1]);
114     _update(root.s[0]);
115 }
116 void mul(int a,int b,int v)
117 {
118     _splay(select(a-1),root.s[0]);
119     _splay(select(b+1),root.s[0]->s[1]);
120     _Node *now=root.s[0]->s[1]->s[0];
121     now->mul=(ll)now->mul*v%MOD;
122     now->add=(ll)now->add*v%MOD;
123     now->v=(ll)now->v*v%MOD;
124 }
125 void add(int a,int b,int v)
126 {
127     _splay(select(a-1),root.s[0]);
128     _splay(select(b+1),root.s[0]->s[1]);
129     _Node *now=root.s[0]->s[1]->s[0];
130     inc(now->add,v);
131     inc(now->v,v);
132 }
133 int get_v(int a,int b,int v)
134 {
135     _splay(select(a-1),root.s[0]);
136     _splay(select(b+1),root.s[0]->s[1]);
137     int now_v=1,ans=0,top;
138     stk[top=1]=root.s[0]->s[1]->s[0];
139     memset(stat,0,sizeof(stat));
140     while (top)
141     {
142         _Node *now=stk[top];
143         if (!stat[now-pool])
144         {
145             _push_down(now);
146             stat[now-pool]=1;
147             if (now->s[0]!=&null) 
148                 stk[++top]=now->s[0];
149             continue;
150         }
151         if (stat[now-pool]==1)
152         {
153             inc(ans,((ll)now->v*now_v)%MOD);
154             stat[now-pool]=2;
155             now_v=((ll)now_v*v)%MOD;
156             continue;
157         }
158         if (stat[now-pool]==2)
159         {
160             if (now->s[1]!=&null)
161                 stk[++top]=now->s[1];
162             stat[now-pool]=3;
163             continue;
164         }
165         --top;
166     }
167     return ans;
168 }
169 int main()
170 {
171     freopen("polynomial.in","r",stdin);
172     freopen("polynomial.out","w",stdout);
173     char opt[10];
174     int x,y,z,n;
175     scanf("%d",&n);
176     init();
177     while (n--)
178     {
179         scanf("%s",opt);
180         switch (opt[0])
181         {
182             case 'a':
183                 scanf("%d%d%d",&x,&y,&z);
184                 add(x+1,y+1,z%MOD);
185                 break;
186             case 'm':
187                 if (opt[3]=='x')
188                 {
189                     scanf("%d%d",&x,&y);
190                     mulx(x+1,y+1);
191                 }
192                 else
193                 {
194                     scanf("%d%d%d",&x,&y,&z);
195                     mul(x+1,y+1,z%MOD);
196                 }
197                 break;
198             case 'q':
199                 scanf("%d",&x);
200                 printf("%d\n",get_v(1,100001,x));
201                 break;
202         }
203     }
204     return 0;
205 }