P3278
pokefunc
·
·
题解
Description
维护一个无穷多项式 a_0x^0+a_1x^1+a_2x^2+\dots，初始所有 a_i=0。
- 将 $a_l,a_{l+1},\dots,a_r$ 加上一个值；
- 将 $a_l,a_{l+1},\dots,a_r$ 乘上一个值；
- 将 $a_l,a_{l+1},\dots,a_r$ 乘上 $x$；
- 给定 $x$，求多项式的值。
$n \le 10^5$，多项式最多 $10^5+1$ 项，求值操作不超过 $10$ 次。
### Sol
由于求值操作不超过 $10$ 次，因此求值可以暴力。
区间加和区间乘都是很简单的线段树操作。
考虑区间乘 $x$ 的实际意义，实际上就是把 $a_l,a_{l+1},\dots,a_r$ 部分整体向右平移一位，将 $a_r$ 与 $a_{r+1}$ 合并，然后将原来 $a_l$ 的地方补上 $0$，于是这就是一个区间平移和插入操作，用平衡树维护即可。
时间复杂度 $\Theta (n \log n)$。
代码用的是简单好写的 $\rm fhqTreap$。
~~能把区间加的懒标记乘上子树大小调了半个小时我都不知道自己在干嘛~~
### Hint
- 注意懒标记的初始化。
- 如果不进行空间回收，数组要开二倍。
- 注意取模，推荐使用 `x=(x%y+y)%y` 防止出现负数。
- 记得开 `long long`。
### Code
```cpp
#include<cstdio>
#include<cstdlib>
#define int long long
const int M=1e5+5;
const int Mod=20130426;
inline int read(){int x(0),op(0);char ch=getchar();while(ch<'0'||ch>'9')op|=(ch==45),ch=getchar();while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();return op?-x:x;}
int pw[M];
namespace Treap{
#define ls(p) t[p].ch[0]
#define rs(p) t[p].ch[1]
struct node{
int val,ch[2],pri,siz;
}t[M<<1];
int at[M<<1],mt[M<<1],rt,nt;//at为加法懒标记，mt为乘法懒标记
void pushup(int p){
t[p].siz=t[ls(p)].siz+t[rs(p)].siz+1;
}
void pushdown(int p){//标记下传
if(mt[p]^1){
t[ls(p)].val*=mt[p];
t[ls(p)].val=(t[ls(p)].val%Mod+Mod)%Mod;
t[rs(p)].val*=mt[p];
t[rs(p)].val=(t[rs(p)].val%Mod+Mod)%Mod;
mt[ls(p)]*=mt[p];
mt[ls(p)]=(mt[ls(p)]%Mod+Mod)%Mod;
mt[rs(p)]*=mt[p];
mt[rs(p)]=(mt[rs(p)]%Mod+Mod)%Mod;
at[ls(p)]*=mt[p];
at[ls(p)]=(at[ls(p)]%Mod+Mod)%Mod;
at[rs(p)]*=mt[p];
at[rs(p)]=(at[rs(p)]%Mod+Mod)%Mod;
mt[p]=1;
}
if(at[p]){
t[ls(p)].val+=at[p];
t[ls(p)].val=(t[ls(p)].val%Mod+Mod)%Mod;
t[rs(p)].val+=at[p];
t[rs(p)].val=(t[rs(p)].val%Mod+Mod)%Mod;
at[ls(p)]+=at[p];
at[ls(p)]=(at[ls(p)]%Mod+Mod)%Mod;
at[rs(p)]+=at[p];
at[rs(p)]=(at[rs(p)]%Mod+Mod)%Mod;
at[p]=0;
}
}
void print(int p){//调试输出树的信息，可以忽略
if(!p)return;
pushdown(p);
print(ls(p));
printf("%lld ",t[p].val);
print(rs(p));
}
void split(int p,int s,int &x,int &y){//fhqTreap split by size
if(!p)return void(x=y=0);
pushdown(p);
int rk=t[ls(p)].siz+1;
if(rk<=s){
x=p;
split(rs(p),s-rk,rs(p),y);
}
else{
y=p;
split(ls(p),s,x,ls(p));
}
pushup(p);
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(t[x].pri<t[y].pri){
pushdown(x);
rs(x)=merge(rs(x),y);
return pushup(x),x;
}
pushdown(y);
ls(y)=merge(x,ls(y));
return pushup(y),y;
}
void insert(int pos,int val){//在位置pos后面插入值val
t[++nt]=(node){val,{0,0},rand(),1};at[nt]=0;mt[nt]=1;
int x,y;
split(rt,pos,x,y);
rt=merge(merge(x,nt),y);
}
void add(int l,int r,int val){//区间加法
int x,y,z;
split(rt,l-1,x,y);
split(y,r-l+1,y,z);
t[y].val+=val;t[y].val=(t[y].val%Mod+Mod)%Mod;
at[y]+=val;at[y]=(at[y]%Mod+Mod)%Mod;
rt=merge(merge(x,y),z);
}
void mult(int l,int r,int val){//区间乘法
int x,y,z;
split(rt,l-1,x,y);
split(y,r-l+1,y,z);
t[y].val*=val;t[y].val=(t[y].val%Mod+Mod)%Mod;
mt[y]*=val;mt[y]=(mt[y]%Mod+Mod)%Mod;
at[y]*=val;at[y]=(at[y]%Mod+Mod)%Mod;
rt=merge(merge(x,y),z);
}
void mulx(int l,int r){//区间乘x
int x,y,z,p,q;
split(rt,l-1,x,y);
split(y,r-l+1,y,z);
split(z,1,z,p);
split(y,r-l,y,q);
/*
这一步分裂完之后的序列被分成了x,y,q,z,p五个部分
将q和z加起来其中一个合并回去即可
*/
t[q].val+=t[z].val;t[q].val=(t[q].val%Mod+Mod)%Mod;
rt=merge(x,merge(y,merge(q,p)));
insert(l-1,0);
}
int qs,tm;
void dfs(int p){//dfs求整个序列的值
if(!p)return;
pushdown(p);
dfs(ls(p));
qs+=pw[++tm]*t[p].val%Mod;qs=(qs%Mod+Mod)%Mod;
dfs(rs(p));
}
int query(int x){//查询
qs=0;tm=-1;
pw[0]=1;
for(int i=1;i<M;++i)pw[i]=(pw[i-1]*x%Mod+Mod)%Mod;//预处理幂
dfs(rt);
return qs;
}
}
using namespace Treap;
signed main(){
int n=read();
for(int i=0;i<M;++i){//插入结点
t[++nt]=(node){0,{0,0},rand(),1};at[nt]=0;mt[nt]=1;
rt=merge(rt,nt);
}
char str[10];
for(int i=1;i<=n;++i){
int l,r;
scanf("%s",str);l=read();
if(str[0]=='q')printf("%lld\n",query(l));
else{
l++;
r=read()+1;
//这里使用+1，防止出现l-1<0的情况
if(str[3]=='x')mulx(l,r);
else{
int x=read();
if(str[0]=='a')add(l,r,x%Mod);
else mult(l,r,x%Mod);
}
}
}
return 0;
}
```