首页 > 代码库 > SCOI2013 多项式的运算 （BZOJ 3323）
SCOI2013 多项式的运算 （BZOJ 3323）
似乎仍然不能附传送门。。权限题T_T...
3323: [Scoi2013]多项式的运算
Time Limit: 12 Sec Memory Limit: 64 MBDescription
某天，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
接下来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
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。
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 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。