题解 P3278 【[SCOI2013]多项式的运算 】
y2823774827y
2019-02-14 12:50:53
第一次打$FHQ-treap$，[更好的阅读体验](https://www.cnblogs.com/y2823774827y/p/10373978.html)，不懂$FHQ-treap$的看[这里](https://www.cnblogs.com/y2823774827y/p/10321171.html)
$(1)(2)$线段树裸题，$(4)$不超过十次暴力即可
主要是处理$(3)$：$k_{l-1}x^{l-1}+k_lx^l+k_{l+1}x^{l+1}+...+k_rx^r+k_{r+1}x^{r+1}\longrightarrow$
$k_{l-1}x^{l-1}+0+k_lx^{l+1}+k_{l+1}x^{l+2}+...(k_r+k_{r+1})x^{r+1}$
把$x$的幂次看作一个序列的顺序，其实就是把$0$插入到$l-1$~$l$，把$k_r$和$k_{r+1}$并起来
区间加，区间乘，插入：平衡树裸题
**细节**：预处理插入节点前面要插入一个虚节点处理$(1)(2)l=0$的特殊情况；其实后面也要插入一些节点处理$(3)r=1e5$的右移情况，数据过水不插也能过
超短的代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline int Read(){
int x(0),f(1);char c=getchar();
while(c<'0' || c>'9'){ if(c=='-')f=-1; c=getchar(); }
while(c>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0', c=getchar();
return x*f;
}
const LL p=20130426;
const int maxn=1e6,N=1e5+1;
LL ret,ans;
int n,root,q,cnt,f;
inline int Rand(){ return rand()%100000; }
struct Treap{
LL key[maxn],lazy1[maxn],lazy2[maxn];
int heap[maxn],size[maxn],son[maxn][2];
inline void Pushdown(LL x){
LL mu(lazy2[x]),ad(lazy1[x]);
int lc(son[x][0]),rc(son[x][1]);
lazy1[x]=0,lazy2[x]=1;
if(mu!=1){
key[lc]=key[lc]*mu%p, lazy1[lc]=lazy1[lc]*mu%p, lazy2[lc]=lazy2[lc]*mu%p;
key[rc]=key[rc]*mu%p, lazy1[rc]=lazy1[rc]*mu%p, lazy2[rc]=lazy2[rc]*mu%p;
}
if(ad){
key[lc]=(key[lc]+ad)%p, lazy1[lc]=(lazy1[lc]+ad)%p;
key[rc]=(key[rc]+ad)%p, lazy1[rc]=(lazy1[rc]+ad)%p;
}
}
inline void Update(int x){
if(!x) return;
size[x]=size[son[x][0]]+size[son[x][1]]+1;
}
int Merge(int x,int y){
if(!x || !y) return x|y;
Pushdown(x),Pushdown(y);
if(heap[x] < heap[y]){
son[x][1]=Merge(son[x][1],y); Update(x); return x;
}else{
son[y][0]=Merge(x,son[y][0]); Update(y); return y;
}
}
void Split_r(int now,int k,int &x,int &y){
if(!now) return (void)(x=y=0);
Pushdown(now);
if(size[son[now][0]]<k)
x=now, Split_r(son[now][1], k-size[son[now][0]]-1, son[x][1], y), Update(x), Update(y);
else
y=now, Split_r(son[now][0], k, x, son[y][0]), Update(x), Update(y);
}
void Query(int now,LL v){
if(!now) return;
Pushdown(now);
Query(son[now][0],v);
ans=(ans+ret*key[now]%p)%p;
if(f) ret=ret*v%p; else f=true;
Query(son[now][1],v);
}
}T;
int main(){
srand(time(NULL));
T.heap[root=++(cnt=N)]=Rand(), T.size[cnt]=T.lazy2[cnt]=1;
for(LL i=1;i<cnt;++i)
T.heap[i]=Rand(), T.size[i]=T.lazy2[i]=1,
root=T.Merge(root,i);
q=Read();
int a,b,c,d,l,r; LL v;
char s[10];
while(q--){
scanf(" %s",s);
if(s[0]=='a'){
l=Read()+1, r=Read()+1, v=Read();
T.Split_r(root,l,a,b), T.Split_r(b,(r-(l-1)),b,c);
T.key[b]=(T.key[b]+v)%p, T.lazy1[b]=(T.lazy1[b]+v)%p;
root=T.Merge(a, T.Merge(b, c));
}else if(s[0]=='q'){
v=Read();
ret=1,ans=f=0;
T.Query(root,v);
printf("%lld\n",ans);
}else{
LL len(strlen(s));
if(len==3){
l=Read()+1, r=Read()+1, v=Read();
T.Split_r(root,l,a,b), T.Split_r(b,(r-(l-1)),b,c);
T.key[b]=(T.key[b]*v)%p, T.lazy1[b]=(T.lazy1[b]*v)%p, T.lazy2[b]=(T.lazy2[b]*v)%p;
root=T.Merge(a, T.Merge(b, c));
}else{
l=Read()+1, r=Read()+1;
T.Split_r(root,r,a,b), T.Split_r(b,1,b,c), T.Split_r(c,1,c,d);
T.key[c]=(T.key[c]+T.key[b])%p;
root=T.Merge(a, T.Merge(c, d));
T.heap[++cnt]=Rand(), T.size[cnt]=T.lazy2[cnt]=1;
T.Split_r(root,l,a,b);
root=T.Merge(a, T.Merge(cnt, b));
}
}
}return 0;
}
```