当前位置：首页 > news >正文

SCOI2013 多项式的运算（BZOJ 3323）

news 来源：原创 2024/5/2 12:21:24

似乎仍然不能附传送门。。权限题T_T...

3323: [Scoi2013]多项式的运算

Time Limit: 12 Sec Memory Limit: 64 MB

Description

某天，mzry1992 一边思考着一个项目问题一边在高速公路上骑着摩托车。一个光头踢了他一脚，摩托车损坏，而他也被送进校医院打吊针。现在该项目的截止日期将近，他不得不请你来帮助他完成这个项目。该项目的目的是维护一个动态的关于x 的无穷多项式F(x) = a0 * x^0 + a1 * x^1 + a2 * x^2 + ... ，这个多项式初始时对于所有i有ai = 0。

操作者可以进行四种操作：

1. 将x^L 到x^R 这些项的系数乘上某个定值v

2. 将x^L 到x^R 这些项的系数加上某个定值v

3. 将x^L 到x^R 这些项乘上x变量

4. 将某个定值v代入多项式F(x)，并输出代入后多项式的值，之后多项式还原为代入前的状况

经过观察，项目组发现使用者的操作集中在前三种，第四种操作不会出现超过10次。mzry1992 负责这个项目的核心代码，你能帮他实现么。

Input

输入的第一行有一个整数n 代表操作的个数。
接下来n 行，每行一个操作，格式如下：
mul L R v 代表第一种操作
add L R v 代表第二种操作
mulx L R 代表第三种操作
query v 代表第四种操作

对于30% 的数据：N <= 5000，0 <= L <= R <= 5000，0 <= v <= 10^9
另有20% 的数据：N <= 10^5，0 <= L <= R <= 10^5，0 <= v <= 10^9，没有mulx 操作
剩下的50% 的数据：N <= 10^5，0 <= L <= R <= 10^5，0 <= v <= 10^9

Output

对于每个query 操作，输出对应的答案，结果可能较大，需要模上20130426。

Sample Input

6
add 0 1 7
query 1
mul 0 1 7
query 2
mulx 0 1
query 3

Sample Output

14
147
588
Hint
操作一之后，多项式为F(x) = 7x + 7。
操作三之后，多项式为F(x) = 49x + 49。
操作五之后，多项式为F(x) = 49x^2 + 49x。

HINT

应上传者要求，此系列试题不公开,如有异议，本站将删除之。

这题写的真特么恶心。。写了两天了。。起初迟迟不写的原因是因为不知道mulx的操作是怎么做的（因为我以为是把整个区间复制粘贴一遍。。后来才知道是平移。。）

讲下各个操作吧：。。好像也没什么操作。。乘法和加法。。与AHOI2009维护seq相似。。注意pushdown！

multx也很好写。。把R-1旋转成树根，把R+1旋转到树根右子树，然后把R合并到R+1上，再在L-1与L之间插入一个数（这里可以用刚才合并的R）

Codes:

  1 #include<set>
  2 #include<queue>
  3 #include<cstdio>
  4 #include<cstdlib>
  5 #include<cstring>
  6 #include<iostream>
  7 #include<algorithm>
  8 using namespace std;
  9 typedef long long LL;
 10 const LL N = 100100;
 11 const LL MOD = 20130426;
 12 #define fa(i) (T[i].p)
 13 #define L(i) (T[i].s[0])
 14 #define R(i) (T[i].s[1])
 15 #define CUR (L(R(root)))
 16 #define Loc(i) (T[fa(i)].s[1] == i)
 17 #define For(i,n) for(LL i=1;i<=n;i++)
 18 #define Rep(i,l,r) for(LL i=l;i<=r;i++)
 19 #define Sets(a,b,c) {if(a) T[a].s[c] = b; if(b) fa(b) = a;}
 20 struct tnode{
 21     LL s[2],p,size;
 22     LL markp,markm,v;
 23 }T[N+100];
 24 char op[10];
 25 LL val,n,l,r,delta,tot,ans,pows = 1;
 26 LL root;
 27  
 28 void Update(LL i){
 29     T[i].size = T[L(i)].size + T[R(i)].size + 1;
 30 }
 31  
 32 void Pushdown(LL i){
 33     if(T[i].markm==1&&T[i].markp==0) return;
 34     if(L(i)){
 35         T[L(i)].markm  = ( T[L(i)].markm * T[i].markm) % MOD;
 36         T[L(i)].markp  = ( T[L(i)].markp * T[i].markm + T[i].markp) % MOD;
 37         T[L(i)].v      = ( T[L(i)].v * T[i].markm + T[i].markp) % MOD;
 38     }  
 39     if(R(i)){
 40         T[R(i)].markm = ( T[R(i)].markm * T[i].markm) % MOD;
 41         T[R(i)].markp  = ( T[R(i)].markp * T[i].markm + T[i].markp) % MOD;
 42         T[R(i)].v      = ( T[R(i)].v * T[i].markm + T[i].markp) % MOD;
 43     }
 44     T[i].markm = 1; T[i].markp = 0;
 45 }
 46  
 47 void Build(LL l,LL r,LL &i,LL p){
 48     if(l>r) return;
 49     T[i=++tot].p = p; T[i].size = T[i].markm = 1; T[i].markp = T[i].v = 0;
 50     LL m = (l+r)>>1;
 51     Build(l,m-1,L(i),i);Build(m+1,r,R(i),i);
 52     Update(i);
 53 }
 54  
 55 LL read(){
 56     LL num = 0; char ch = getchar();
 57     while(ch<'0'||ch>'9') ch = getchar();
 58     while((ch>='0')&&(ch<='9')){
 59         num = num * 10 + ch - '0';
 60         ch = getchar();
 61     }
 62     return num;
 63 }
 64  
 65 void Clear(LL i){
 66     T[i].p = T[i].markp = T[i].size = T[i].v = 0;
 67     T[i].markm = 1;
 68 }
 69  
 70 void Rot(LL x){
 71     LL y = fa(x) , z = fa(y);
 72     Pushdown(y); Pushdown(x);
 73     LL lx = Loc(x) , ly = Loc(y);
 74     Sets(y,T[x].s[!lx],lx);
 75     Sets(z,x,ly);
 76     Sets(x,y,!lx);
 77     Update(y);
 78 }
 79  
 80 void Splay(LL i,LL goal){
 81     while(fa(i)!=goal){
 82         if(fa(fa(i))!=goal) Rot(fa(i));
 83         Rot(i);
 84     }
 85     Update(i);
 86     if(!goal) root = i;
 87 }
 88  
 89 bool dlim = false;
 90  
 91 void query(LL val,LL i){
 92     Pushdown(i);
 93     if(L(i)) query(val,L(i));
 94     if(!dlim)   dlim = true;
 95     else      { ans = ( ans + (T[i].v * pows) % MOD ) % MOD; pows = ( pows * val ) % MOD;}
 96     if(R(i)) query(val,R(i));
 97 }
 98  
 99 LL Rank(LL kth,LL i){
100     Pushdown(i);
101     if(T[L(i)].size + 1 == kth) return i;
102     else if(T[L(i)].size>= kth) return Rank(kth,L(i));
103     else                        return Rank(kth - T[L(i)].size - 1 , R(i));
104 }
105  
106 int main(){
107     n = read();
108     Build(0,N,root,0);
109     For(i,n){
110         scanf("%s",&op);
111         if(op[0]=='q'){
112             val = read();dlim = false;pows = 1;
113             query(val,root);
114             printf("%lld\n",ans);
115             ans = 0;
116         }
117         else{
118             l = read(); r = read();
119             l++;r++;
120             if(op[0]=='a'){
121                 val = read();
122                 Splay(Rank(l,root),0);
123                 Splay(Rank(r+2,root),root);
124                 T[CUR].markp = (T[CUR].markp + val) % MOD;
125                 T[CUR].v     = (T[CUR].v     + val) % MOD;
126             }
127             else if(op[3]=='x'){
128                 Splay(Rank(r,root),0);Splay(Rank(r+2,root),root);
129                 LL tcur = CUR;
130                 T[R(root)].v = ( T[R(root)].v + T[CUR].v ) % MOD;
131                 Clear(CUR);T[R(root)].s[0] = 0;
132                 Update(R(root)); Update(root);
133                 Splay(Rank(l,root),0);Splay(Rank(l+1,root),root);
134                 Sets(R(root),tcur,0);T[tcur].size = 1;
135                 Update(R(root)); Update(root);
136             }
137             else{
138                 val = read();
139                 Splay(Rank(l,root),0);
140                 Splay(Rank(r+2,root),root);
141                 T[CUR].markp = (T[CUR].markp * val) % MOD;
142                 T[CUR].markm = (T[CUR].markm * val) % MOD;
143                 T[CUR].v     = (T[CUR].v     * val) % MOD;
144             }
145         }
146     }
147     return 0;
148 }