传送门
这个GSSGSSGSS系列全部是跟子段有关的数据结构菜题。
于是来水一篇博客。
GSS1
传送门
题意简述：求不带修的最大子段和。
思路：直接线段树走一发。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=5e4+5;
int n,a[N];
inline int max(const int&a,const int&b){return a>b?a:b;}
inline int max(const int&a,const int&b,const int&c){return a>b?(a>c?a:c):(b>c?b:c);}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
struct Val{
int ls,rs,ms,sum;
inline void init(const int&x){ls=rs=ms=sum=x;}
};
inline Val operator+(const Val&a,const Val&b){return (Val){max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}
struct Node{int l,r;Val val;}T[N<<2];
inline void pushup(int p){T[p].val=T[lc].val+T[rc].val;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r)return T[p].val.init(a[l]);
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline Val query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,qr)+query(rc,ql,qr);
}
}
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f^=1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return f?ans:-ans;
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read();
SGT::build(1,1,n);
for(ri tt=read(),x;tt;--tt)x=read(),cout<<SGT::query(1,x,read()).ms<<'\n';
return 0;
}
GSS2
传送门
唯一感觉有点思维难度的题。
题意简述：求不带修的最大子段和，对于一个子段里面同一个数值只能产生一次贡献。
思路：
考虑离线询问。
我们对于第iii次询问(l,r)(l,r)(l,r)把它扔进一个用vectorvectorvector储存的qryqryqry数组中，即qryr.push_back(l,i)qry_r.push\_back(l,i)qryr.push_back(l,i)，然后我们从左往右加点。
当处理到这个询问的时候，相当于只用问对于所有下标在[l,r][l,r][l,r]之间的点，以它们为左端点开始向右延伸的最大子段的最大值是多少。
这个东西怎么维护？
我们用增量构造法，考虑把前面的在i−1i-1i−1结尾的所有子段即[1,i−1],[2,i−1],...,[i−1,i−1][1,i-1],[2,i-1],...,[i-1,i-1][1,i−1],[2,i−1],...,[i−1,i−1]这些子段同时加上一个aia_iai去更新111~i−1i-1i−1处的答案。
这样我们实际上对于一个点iii只需要维护两个东西：
- Sum(i,now)Sum(i,now)Sum(i,now)，这个SumSumSum的求法是题意的求法，即相同的值只算一次。
- hisSum(i,now)=max(Sum(i,i),Sum(i,i+1),..,Sum(i,now))hisSum(i,now)=max(Sum(i,i),Sum(i,i+1),..,Sum(i,now))hisSum(i,now)=max(Sum(i,i),Sum(i,i+1),..,Sum(i,now))
考虑每次加一个值aia_iai对于前面所有点的贡献。
记preipre_iprei表示上一个aia_iai出现的位置，那么对于那些下标在[1,prei][1,pre_i][1,prei]之间的点它们的SumSumSum和hisSumhisSumhisSum是不变的（因为加上这个值的贡献会扣掉preipre_iprei那个位置的贡献）
而对于[prei+1,i−1][pre_i+1,i-1][prei+1,i−1]的点它们的SumSumSum全部会加上SumSumSum。
于是用线段树更新[prei+1,i−1][pre_i+1,i-1][prei+1,i−1]的和以及历史和最值即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f^=1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return f?ans:-ans;
}
const int N=1e5+5;
int n,a[N],pre[N],m;
ll ans[N];
struct qry{int l,id;};
vector<qry>q[N];
map<int,int>mp;
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
struct Tag{ll add,hadd;};
struct Val{ll sum,hsum;};
const Tag tag_empty=(Tag){0ll,0ll};
struct Node{int l,r;ll mx;Val val;Tag tag;}T[N<<2];
inline Val operator+(const Val&a,const Val&b){return (Val){max(a.sum,b.sum),max(a.hsum,b.hsum)};}
inline Val operator+(const Val&a,const Tag&b){return (Val){a.sum+b.add,max(a.hsum,a.sum+b.hadd)};}
inline void operator+=(Val&a,const Tag&b){a=a+b;}
inline Tag operator+(const Tag&a,const Tag&b){return (Tag){a.add+b.add,max(a.hadd,a.add+b.hadd)};}
inline void operator+=(Tag&a,const Tag&b){a=a+b;}
inline bool operator==(const Tag&a,const Tag&b){return a.add==b.add&&a.hadd==b.hadd;}
inline void pushup(int p){T[p].val=T[lc].val+T[rc].val;}
inline void pushnow(int p,Tag v){T[p].val+=v,T[p].tag+=v;}
inline void pushdown(int p){
if(T[p].tag==tag_empty)return;
pushnow(lc,T[p].tag),pushnow(rc,T[p].tag);
T[p].tag=tag_empty;
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].tag=tag_empty;
if(T[p].l==T[p].r){T[p].val=(Val){a[l],a[l]};return;}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int ql,int qr,int v){
if(ql>qr)return;
if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,(Tag){v,v});
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,qr,v),update(rc,ql,qr,v);
pushup(p);
}
inline ll query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr)return T[p].val.hsum;
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return max(query(lc,ql,qr),query(rc,ql,qr));
}
#undef lc
#undef rc
#undef mid
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read(),pre[i]=mp[a[i]+100001],mp[a[i]+100001]=i;
SGT::build(1,1,n);
m=read();
for(ri l,r,i=1;i<=m;++i)l=read(),r=read(),q[r].push_back((qry){l,i});
for(ri i=1;i<=n;++i){
SGT::update(1,pre[i]+1,i-1,a[i]);
for(ri j=0;j<q[i].size();++j)ans[q[i][j].id]=SGT::query(1,q[i][j].l,i);
}
for(ri i=1;i<=m;++i)cout<<max(ans[i],0ll)<<'\n';
return 0;
}
GSS3
传送门
题意简述：单点修改维护最大子段和。
思路：直接上线段树即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=5e4+5;
int n,a[N];
inline int max(const int&a,const int&b){return a>b?a:b;}
inline int max(const int&a,const int&b,const int&c){return a>b?(a>c?a:c):(b>c?b:c);}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
struct Val{
int ls,rs,ms,sum;
inline void init(const int&x){ls=rs=ms=sum=x;}
};
inline Val operator+(const Val&a,const Val&b){return (Val){max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}
struct Node{int l,r;Val val;}T[N<<2];
inline void pushup(int p){T[p].val=T[lc].val+T[rc].val;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r)return T[p].val.init(a[l]);
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int k,int v){
if(T[p].l==T[p].r)return T[p].val.init(v);
update(k<=mid?lc:rc,k,v),pushup(p);
}
inline Val query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,qr)+query(rc,ql,qr);
}
}
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f^=1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return f?ans:-ans;
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read();
SGT::build(1,1,n);
for(ri tt=read(),op,x,y;tt;--tt){
op=read(),x=read(),y=read();
if(!op)SGT::update(1,x,y);
else cout<<SGT::query(1,x,y).ms<<'\n';
}
return 0;
}
GSS4
传送门
题意简述：支持区间开方，区间求和。
思路：线段树套路题，区间最大值大于111递归修改否则直接返回。
每个数被开方log(logn)log(log_n)log(logn)次之后就没了。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
ll a[N];
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
struct Node{int l,r;ll mx,sum;}T[N<<2];
inline void pushup(int p){
T[p].mx=max(T[lc].mx,T[rc].mx);
T[p].sum=T[lc].sum+T[rc].sum;
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r){T[p].sum=T[p].mx=a[l];return;}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int ql,int qr){
if(T[p].mx<2)return;
if(T[p].l==T[p].r){T[p].sum=T[p].mx=sqrt(T[p].mx);return;}
if(qr<=mid)update(lc,ql,qr);
else if(ql>mid)update(rc,ql,qr);
else update(lc,ql,qr),update(rc,ql,qr);
pushup(p);
}
inline ll query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr)return T[p].sum;
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,qr)+query(rc,ql,qr);
}
#undef lc
#undef rc
#undef mid
}
int main(){
int cas=0;
while(~scanf("%d",&n)){
++cas;
printf("Case #%d:\n",cas);
for(ri i=1;i<=n;++i)a[i]=read();
SGT::build(1,1,n);
for(ri tt=read(),op,l,r;tt;--tt){
op=read(),l=read(),r=read();
if(l>r)swap(l,r);
if(!op)SGT::update(1,l,r);
else cout<<SGT::query(1,l,r)<<'\n';
}
puts("");
}
return 0;
}
GSS5
传送门
题意简述：
求左端点在[l1,r1][l1,r1][l1,r1]，右端点在[l2,r2][l2,r2][l2,r2]之间的最大子段和。
思路：直接分[l1,r1],[l2,r2][l1,r1],[l2,r2][l1,r1],[l2,r2]是否相交讨论一下，之后就是最大子段和问题了。
不相交⇒[l1,r1]\Rightarrow[l1,r1]⇒[l1,r1]中最大后缀和+sumr1+1,l2−1+[l2,r2]+sum_{r1+1,l2-1}+[l2,r2]+sumr1+1,l2−1+[l2,r2]中最大前缀和。
相交⇒\Rightarrow⇒讨论l1l1l1与l2l2l2关系，r1r1r1与r2r2r2关系更新答案。
代码：
#include<bits/stdc++.h>
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
#define N 10005
using namespace std;
inline int read(){
int ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,m,a[N],T_T;
struct Node{int l,r,ls,rs,ms,sum;}T[N<<2];
inline Node operator+(const Node&a,const Node&b){
Node ret;
ret.l=a.l,ret.r=b.r,ret.sum=a.sum+b.sum;
ret.ls=max(a.ls,a.sum+b.ls);
ret.rs=max(b.rs,b.sum+a.rs);
ret.ms=max(max(a.ms,b.ms),a.rs+b.ls);
return ret;
}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r;
if(l==r){T[p].ls=T[p].rs=T[p].ms=T[p].sum=a[l];return;}
build(lc,l,mid),build(rc,mid+1,r),T[p]=T[lc]+T[rc];
}
inline Node query(int p,int ql,int qr){
if(ql>T[p].r||qr<T[p].l)return (Node){T[p].l,T[p].r,0,0,0,0};
if(ql<=T[p].l&&T[p].r<=qr)return T[p];
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,mid)+query(rc,mid+1,qr);
}
int main(){
T_T=read();
while(T_T--){
n=read();
for(int i=1;i<=n;++i)a[i]=read();
build(1,1,n),m=read();
while(m--){
int l1=read(),r1=read(),l2=read(),r2=read();
if(r1<l2){
Node ansl=query(1,l1,r1),ansm=query(1,r1+1,l2-1),ansr=query(1,l2,r2);
printf("%d\n",ansl.rs+ansm.sum+ansr.ls);
}
else{
int ans=query(1,l2,r1).ms;
if(l1<l2)ans=max(ans,query(1,l1,l2).rs+query(1,l2,r2).ls-a[l2]);
if(r2>r1)ans=max(ans,query(1,l1,r1).rs+query(1,r1,r2).ls-a[r1]);
printf("%d\n",ans);
}
}
}
return 0;
}
GSS6
传送门
题意简述：支持在序列中插入，删除，修改某个数的值，询问最大子段和。
思路：把最大子段和的求法搬上fhq_treapfhq\_treapfhq_treap即可。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return f?ans:-ans;
}
typedef long long ll;
typedef pair<int,int> pii;
const int N=2e5+5;
int n;
char s[2];
inline int max(const ll&a,const ll&b){return a>b?a:b;}
inline int max(const ll&a,const ll&b,const ll&c){return a>b?(a>c?a:c):(b>c?b:c);}
namespace Bst{
#define lc (son[p][0])
#define rc (son[p][1])
struct Val{
ll ls,rs,ms,sum;
inline void init(const ll&x){ls=rs=ms=sum=x;}
};
inline Val operator+(const Val&a,const Val&b){return (Val){max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}
int rt=0,tot=0,son[N][2],siz[N],rd[N],val[N];
Val f[N];
inline int build(int v){return val[++tot]=v,rd[tot]=rand(),siz[tot]=1,son[tot][0]=son[tot][1]=0,f[tot].init(v),tot;}
inline void pushup(int p){
siz[p]=siz[lc]+1+siz[rc];
f[p].init(val[p]);
if(lc)f[p]=f[lc]+f[p];
if(rc)f[p]=f[p]+f[rc];
}
inline int merge(int a,int b){
if(!a||!b)return a+b;
if(rd[a]>rd[b])return son[a][1]=merge(son[a][1],b),pushup(a),a;
return son[b][0]=merge(a,son[b][0]),pushup(b),b;
}
inline pii split(int p,int k){
if(!p)return pii(0,0);
pii tmp;
if(siz[lc]>=k)return tmp=split(lc,k),lc=tmp.se,pushup(p),pii(tmp.fi,p);
return tmp=split(rc,k-siz[lc]-1),rc=tmp.fi,pushup(p),pii(p,tmp.se);
}
inline void insert(int id,int v){
pii x=split(rt,id-1);
rt=merge(merge(x.fi,build(v)),x.se);
}
inline void delet(int id){
pii x=split(rt,id-1),y=split(x.se,1);
rt=merge(x.fi,y.se);
}
inline void update(int id,int v){
pii x=split(rt,id-1),y=split(x.se,1);
val[y.fi]=v,f[y.fi].init(v);
rt=merge(merge(x.fi,y.fi),y.se);
}
inline void query(int l,int r){
pii x=split(rt,l-1),y=split(x.se,r-l+1);
cout<<f[y.fi].ms<<'\n';
rt=merge(x.fi,merge(y.fi,y.se));
}
#undef lc
#undef rc
}
int main(){
srand(time(NULL));
n=read();
for(ri i=1;i<=n;++i)Bst::insert(i,read());
for(ri p,x,tt=read();tt;--tt){
scanf("%s",s);
if(s[0]=='I')p=read(),x=read(),Bst::insert(p,x);
if(s[0]=='D')p=read(),Bst::delet(p);
if(s[0]=='R')p=read(),x=read(),Bst::update(p,x);
if(s[0]=='Q')p=read(),x=read(),Bst::query(p,x);
}
return 0;
}
GSS7
传送门
题意简述：支持给一棵树路径赋值，求最大子路径。
思路：最大子段和搬上树链剖分即可，注意合并时候的顺序这点小细节就很简单了。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=1e5+5,inf=1e9;
int n,tot=0,a[N],num[N],dep[N],top[N],fa[N],hson[N],siz[N],pred[N];
vector<int>e[N];
void dfs1(int p){
siz[p]=1;
for(ri i=0,v;i<e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
fa[v]=p,dep[v]=dep[p]+1,dfs1(v),siz[p]+=siz[v];
if(siz[v]>siz[hson[p]])hson[p]=v;
}
}
void dfs2(int p,int tp){
top[p]=tp,pred[num[p]=++tot]=p;
if(!hson[p])return;
dfs2(hson[p],tp);
for(ri i=0,v;i<e[p].size();++i)if((v=e[p][i])!=fa[p]&&v!=hson[p])dfs2(v,v);
}
inline int max(const int&a,const int&b){return a>b?a:b;}
inline int max(const int&a,const int&b,const int&c){return a>b?(a>c?a:c):(b>c?b:c);}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (T[p].l+T[p].r>>1)
struct Val{int ls,rs,ms,sum;};
inline Val operator+(const Val&a,const Val&b){return (Val){max(a.ls,a.sum+b.ls),max(b.rs,b.sum+a.rs),max(a.ms,b.ms,a.rs+b.ls),a.sum+b.sum};}
struct Node{
int l,r,cov;Val val;
inline void init(const int&x){
val.sum=(r-l+1)*x;
if(x>0)val.ls=val.rs=val.ms=val.sum;
else val.ls=val.rs=val.ms=x;
}
}T[N<<2];
inline void pushup(int p){T[p].val=T[lc].val+T[rc].val;}
inline void pushnow(int p,int v){T[p].init(v),T[p].cov=v;}
inline void pushdown(int p){if(inf^T[p].cov)pushnow(lc,T[p].cov),pushnow(rc,T[p].cov),T[p].cov=inf;}
inline void build(int p,int l,int r){
T[p].l=l,T[p].r=r,T[p].cov=inf;
if(l==r)return T[p].init(a[pred[l]]);
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline void update(int p,int ql,int qr,int v){
if(ql<=T[p].l&&T[p].r<=qr)return pushnow(p,v);
pushdown(p);
if(qr<=mid)update(lc,ql,qr,v);
else if(ql>mid)update(rc,ql,qr,v);
else update(lc,ql,qr,v),update(rc,ql,qr,v);
pushup(p);
}
inline Val query(int p,int ql,int qr){
if(ql<=T[p].l&&T[p].r<=qr)return T[p].val;
pushdown(p);
if(qr<=mid)return query(lc,ql,qr);
if(ql>mid)return query(rc,ql,qr);
return query(lc,ql,qr)+query(rc,ql,qr);
}
inline int query(int p,int k){
if(T[p].l==T[p].r)return T[p].val.sum;
pushdown(p);
return query(k<=mid?lc:rc,k);
}
#undef lc
#undef rc
#undef mid
}
inline void update(int x,int y,int v){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
SGT::update(1,num[top[x]],num[x],v),x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
SGT::update(1,num[y],num[x],v);
}
inline int lca(int x,int y){
while(top[x]^top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
inline int query(int x,int y){
int t=lca(x,y);
SGT::Val ta=(SGT::Val){0,0,0,0},tb=(SGT::Val){0,0,0,0};
while(top[x]^top[t])ta=SGT::query(1,num[top[x]],num[x])+ta,x=fa[top[x]];
ta=SGT::query(1,num[t],num[x])+ta;
while(top[y]^top[t])tb=SGT::query(1,num[top[y]],num[y])+tb,y=fa[top[y]];
tb=SGT::query(1,num[t],num[y])+tb;
return max(ta.ms,tb.ms,ta.ls+tb.ls-SGT::query(1,num[t]));
}
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f^=1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return f?ans:-ans;
}
int main(){
n=read();
for(ri i=1;i<=n;++i)a[i]=read();
for(ri i=1,u,v;i<n;++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs1(1),dfs2(1,1),SGT::build(1,1,n);
for(ri tt=read(),op,l,r;tt;--tt){
op=read(),l=read(),r=read();
if(op==1)cout<<query(l,r)<<'\n';
else update(l,r,read());
}
return 0;
}
GSS8
传送门
题意简述：支持给一个序列插入，删除，修改某个数的值。
支持查询f(l,r,k)=∑i=lrai(i−l+1)k,0≤k≤10f(l,r,k)=\sum_{i=l}^ra_i(i-l+1)^k,0\le k\le10f(l,r,k)=∑i=lrai(i−l+1)k,0≤k≤10
思路：
显然除了查询外的都是fhqtreapfhq_treapfhqtreap常规操作。
然后只用考虑如何维护答案，由于每次的kkk一样，因此我们每个treaptreaptreap节点 对于k=0→10k=0\rightarrow10k=0→10都维护一个答案。
考虑合并a,ba,ba,b的答案。
aaa对于答案的贡献就是本身， 但是bbb不太一样。
本来假设是∑(x+t)k→∑(x+t+siza)k\sum(x+t)^k\rightarrow\sum(x+t+siz_a)^k∑(x+t)k→∑(x+t+siza)k我们发现sizasiz_asiza是定值，于是可以将x+tx+tx+t看成yyy，我们已经知道y0,y1,...,y10y^0,y^1,...,y^10y0,y1,...,y10了，于是可以二项式展开(y+siza)k=∑i=0kCkiyisizak−i(y+siz_a)^k=\sum_{i=0}^kC_k^iy^isiz_a^{k-i}(y+siza)k=∑i=0kCkiyisizak−i，我们每次预处理一个siza0→10siz_a^{0\rightarrow10}siza0→10转移即可。
代码：
#include<bits/stdc++.h>
#define ri register int
#define fi first
#define se second
using namespace std;
typedef unsigned int ll;
typedef pair<int,int> pii;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=2e5+5;
int n;
ll pmul[11],C[11][11];
inline void init(){
for(ri i=0;i<=10;++i){
C[i][0]=C[i][i]=1;
for(ri j=1;j<i;++j)C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
namespace Bst{
#define lc (son[p][0])
#define rc (son[p][1])
struct Val{
ll s[11];int siz;
inline void init(const ll&v){
siz=1;
for(ri i=0;i<=10;++i)s[i]=v;
}
}val[N];
int son[N][2],a[N],rd[N],rt=0,tot=0;
inline Val operator+(const Val&a,const Val&b){
Val ret;
ret.siz=a.siz+b.siz;
pmul[0]=1;
for(ri i=1;i<=10;++i)pmul[i]=pmul[i-1]*a.siz;
for(ri i=0;i<=10;++i){ret.s[i]=a.s[i];for(ri j=0;j<=i;++j)ret.s[i]+=C[i][j]*b.s[j]*pmul[i-j];}
return ret;
}
inline int build(ll v){return a[++tot]=v,rd[tot]=rand(),son[tot][0]=son[tot][1]=0,val[tot].init(v),tot;}
inline void pushup(int p){
val[p].init(a[p]);
if(lc)val[p]=val[lc]+val[p];
if(rc)val[p]=val[p]+val[rc];
}
inline int merge(int a,int b){
if(!a||!b)return a+b;
if(rd[a]>rd[b])return son[a][1]=merge(son[a][1],b),pushup(a),a;
return son[b][0]=merge(a,son[b][0]),pushup(b),b;
}
inline pii split(int p,int k){
if(!p)return pii(0,0);
pii tmp;
if(val[lc].siz>=k)return tmp=split(lc,k),lc=tmp.se,pushup(p),pii(tmp.fi,p);
return tmp=split(rc,k-val[lc].siz-1),rc=tmp.fi,pushup(p),pii(p,tmp.se);
}
inline void insert(int id,ll v){
pii x=split(rt,id-1);
rt=merge(x.fi,merge(build(v),x.se));
}
inline void delet(int id){
pii x=split(rt,id-1),y=split(x.se,1);
rt=merge(x.fi,y.se);
}
inline void update(int id,ll v){
pii x=split(rt,id-1),y=split(x.se,1);
val[y.fi].init(a[y.fi]=v),rt=merge(x.fi,merge(y.fi,y.se));
}
inline void query(int l,int r,int k){
pii x=split(rt,l-1),y=split(x.se,r-l+1);
cout<<val[y.fi].s[k]<<'\n';
rt=merge(x.fi,merge(y.fi,y.se));
}
#undef lc
#undef rc
}
char s[5];
int main(){
srand(time(NULL));
n=read(),init();
for(ri i=1;i<=n;++i)Bst::insert(i,read());
for(ri l,r,x,tt=read();tt;--tt){
scanf("%s",s);
if(s[0]=='Q')l=read()+1,r=read()+1,Bst::query(l,r,read());
if(s[0]=='I')x=read()+1,Bst::insert(x,read());
if(s[0]=='D')x=read()+1,Bst::delet(x);
if(s[0]=='R')x=read()+1,Bst::update(x,read());
}
return 0;
}