3323: [Scoi2013]多项式的运算
Time Limit: 12 Sec Memory Limit: 64 MB
Submit: 128 Solved: 33
[Submit][Status]
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 代表第四种操作
接下来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
应上传者要求，此系列试题不公开,如有异议，本站将删除之。
Source
题解：
splay
比较麻烦的是第三种操作，我们将r与r+1的系数合并，然后在l处插入一个0，就完成了系数的平移。orz jcvb！
然后第四种操作暴力遍历树就可以了
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 1000000+100
#define maxm 100000+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 20130426
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
int q,rt,t1,t2,tot,s[maxn],c[maxn][],fa[maxn];
ll v[maxn],t[maxn][],ans,base;
inline void pushup(int x)
{
s[x]=s[c[x][]]+s[c[x][]]+;
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y],l=c[y][]==x,r=l^;
if(y!=k)c[z][c[z][]==y]=x;else k=x;
fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
c[y][l]=c[x][r];c[x][r]=y;
pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if(c[z][]==y^c[y][]==x)rotate(x,k);else rotate(y,k);
}
rotate(x,k);
}
}
inline void update(int x,ll xx,ll yy)
{
if(!x)return;
(v[x]=v[x]*yy+xx)%=mod;
((t[x][]*=yy)+=xx)%=mod;
(t[x][]*=yy)%=mod;
}
inline void pushdown(int x)
{
if(!x)return;
if(!t[x][]&&t[x][]==)return;
update(c[x][],t[x][],t[x][]);
update(c[x][],t[x][],t[x][]);
t[x][]=;t[x][]=;
}
inline int find(int x,int k)
{
pushdown(x);
int l=c[x][],r=c[x][];
if(s[l]+==k)return x;
else if(s[l]>=k)return find(l,k);
else return find(r,k-s[l]-);
}
inline void split(int l,int r)
{
t1=find(rt,l);t2=find(rt,r);
splay(t1,rt);splay(t2,c[t1][]);
}
inline void calc(int x)
{
if(!x)return;
pushdown(x);
calc(c[x][]);
if(x!=)ans=(ans*base+v[x])%mod;
calc(c[x][]);
}
inline void build(int l,int r,int f)
{
if(l>r)return;
int x=(l+r)>>;
fa[x]=f;c[f][x>f]=x;
s[x]=;t[x][]=;t[x][]=;
if(l==r)return;
build(l,x-,x);build(x+,r,x);
pushup(x);
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
build(,maxm,);tot=maxm;rt=(+maxm)>>;
q=read();char ch[maxn];
while(q--)
{
scanf("%s",ch);
if(ch[]=='q')
{
ans=;base=read()%mod;
calc(rt);
cout<<ans<<endl;
}
else
{
int x=read()+,y=read()+;
if(ch[]=='x')
{
split(y,y+);
int z=c[t2][],zz=c[z][]+c[z][];
pushdown(t1);pushdown(t2);pushdown(z);
v[z]+=v[zz];s[z]=;
fa[zz]=c[z][]=c[z][]=;
pushup(t2);pushup(t1);
split(x,x+);
c[t2][]=++tot;s[tot]=;v[tot]=;fa[tot]=t2;t[tot][]=;
pushup(t2);pushup(t1);
}
else if(ch[]=='m')
{
split(x,y+);
ll xx=,yy=read()%mod;
update(c[t2][],xx,yy);
pushup(t2);pushup(t1);
}
else
{
split(x,y+);
ll xx=read()%mod,yy=;
update(c[t2][],xx,yy);
pushup(t2);pushup(t1);
}
}
}
return ;
}