这一道题的修改操作用平衡树都很容易实现，难处理的是询问操作。
要想解决询问操作，只要知道如何在平衡树上快速合并左右两个区间的答案即可。
设$Ans_{[l,r]}^k=sumlimits_{i=l}^rA(i)cdot(i-l+1)^k$。
设现在要处理的区间为$[x,y]$，中间位置为$mid$，已知$Ans_{[x,mid-1]}^k$和$Ans_{[mid+1,y]}^k$,要求$Ans_{[x,y]}^k$。
显然，$Ans_{[x,y]}^k=Ans_{[x,mid-1]}^k+A(mid)cdot(mid-l+1)^k+sumlimits_{i=mid+1}^yA(i)cdot(i-x+1)^k$。
观察式子，发现最左边的部分已知，中间的部分容易求得，关键是要快速求出最右边的部分。
从充分利用已知信息的角度考虑，我们可以先试图让最右边的部分和$Ans_{[mid+1,y]}^k$扯上关系。
于是我们就这样变：
$sumlimits_{i=mid+1}^yA(i)cdot(i-x+1)^k=sumlimits_{i=mid+1}^yA(i)cdot(i-mid+mid-x+1)^k$。
那个$i-mid$可以看成是$i-(mid+1)+1$，是$Ans_{[mid+1,y]}^k$展开后里面的一部分，于是我们考虑令$s=mid-x+1$。
那么原式就可变成这样子：
$sumlimits_{i=mid+1}^yA(i)cdot(i-x+1)^k=sumlimits_{i=mid+1}^yA(i)cdot(i-mid+s)^k$。
更据二项式定理，可得：
$sumlimits_{i=mid+1}^yA(i)cdot(i-x+1)^k=sumlimits_{i=mid+1}^yA(i)cdotsumlimits_{j=0}^kC_k^j(i-mid)^js^{k-j}$。
把$A(i)$扔进最里面的那个求和里，可得：
$sumlimits_{i=mid+1}^yA(i)cdot(i-x+1)^k=sumlimits_{i=mid+1}^ysumlimits_{j=0}^kA(i)cdot(i-mid)^jC_k^js^{k-j}$。
交换一下里外的两层求和，再把$C_k^js^{k-j}$提出来，可得:
$sumlimits_{i=mid+1}^yA(i)cdot(i-x+1)^k=sumlimits_{j=0}^kC_k^js^{k-j}sumlimits_{i=mid+1}^yA(i)cdot(i-mid)^j$。
然后我们可以发现里面的那层求和的形式和询问的式子的一模一样，于是我们就有：
$sumlimits_{i=mid+1}^yA(i)cdot(i-x+1)^k=sumlimits_{j=0}^kC_k^js^{k-j}Ans_{[mid+1,y]}^j$。
那么，对于平衡树上每一个节点所代表的区间，我们可以把每一种$k$的答案都存起来，再预处理组合数，这样我们就可以用$O(k^2)$的时间完成对两个区间答案的合并，按照上面得到的结果计算即可。由于$k$很小，所以这个时间复杂度还是可以接受的。
至此，这道题的难点就解决了。
坑点：这道题是对$2^{32}$取模，计算过程中又有乘法，所以中间结果会爆long long，所以应该用unsigned long long存储和计算答案。
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MxK=10; const unsigned long long INF=1e18; const unsigned long long mod=((long long)1<<32); struct Data { int Fa,Siz,Son[2]; unsigned long long Val,Ans[11]; }S[200005]; int tot=0,Root=0; unsigned long long ml[12],Num[100005],C[12][12]; inline long long rdin() { char ch=getchar(); register long long x=0; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-48,ch=getchar(); return x; } void Csh() { S[0].Siz=0; for(int i=0;i<=MxK;i++) C[i][0]=1,S[0].Ans[i]=0; for(int i=1;i<=MxK;i++) for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; } int NewNode(unsigned long long w) { int x=++tot; S[x].Siz=1,S[x].Val=w; S[x].Son[0]=S[x].Son[1]=0; for(int i=0;i<=MxK;i++) S[x].Ans[i]=w; return x; } void PushUp(int p) { int L=S[p].Son[0]; int R=S[p].Son[1]; int l=1,mid=S[L].Siz+1; int x=mid-l+1; unsigned long long s=1; ml[0]=1; for(int i=1;i<=MxK;i++) ml[i]=ml[i-1]*x%mod; for(register int k=0;k<=MxK;k++) { unsigned long long w=0; for(int i=0;i<=k;i++) w=(w+ml[k-i]*C[k][i]%mod*S[R].Ans[i]%mod)%mod; S[p].Ans[k]=(S[L].Ans[k]+S[p].Val*s%mod+w)%mod; s=s*x%mod; } S[p].Siz=S[L].Siz+S[R].Siz+1; } int BuildTree(int l,int r) { if(l>r) return 0; int mid=(l+r)>>1; int u=NewNode((Num[mid]==-INF)?0:Num[mid]); S[u].Son[0]=BuildTree(l,mid-1); S[u].Son[1]=BuildTree(mid+1,r); if(S[u].Son[0]) S[S[u].Son[0]].Fa=u; if(S[u].Son[1]) S[S[u].Son[1]].Fa=u; PushUp(u); return u; } int GetP(int x) {return S[S[x].Fa].Son[1]==x;} void Rotate(int x) { int p=GetP(x),f=S[x].Fa; if(S[f].Fa) S[S[f].Fa].Son[GetP(f)]=x; S[x].Fa=S[f].Fa; if(S[x].Son[p^1]) S[S[x].Son[p^1]].Fa=f; S[f].Son[p]=S[x].Son[p^1]; S[x].Son[p^1]=f,S[f].Fa=x; PushUp(f); } void Splay(int x) { while(S[x].Fa) { if(S[S[x].Fa].Fa&&GetP(x)==GetP(S[x].Fa)) Rotate(S[x].Fa); Rotate(x); } PushUp(x),Root=x; } int FindKth(int p,int k) { int c=S[S[p].Son[0]].Siz+1; if(c==k) return p; if(c<k) return FindKth(S[p].Son[1],k-c); return FindKth(S[p].Son[0],k); } void SplitTree(int p,int k,int &x,int &y) { x=FindKth(p,k),Splay(x); y=S[x].Son[1],S[y].Fa=0,S[x].Son[1]=0; PushUp(x); } int MergeTrees(int x,int y) { Splay(x),Splay(y); while(S[x].Son[1]) x=S[x].Son[1]; Splay(x),S[x].Son[1]=y,S[y].Fa=x; PushUp(x); return x; } void ChangeNode(int x,int w) { S[x].Val=w; for(int i=0;i<=MxK;i++) S[x].Ans[i]=w; } void InsertVal(int x,int w) { int u=NewNode(w); x=FindKth(Root,x-1),Splay(x); x=S[x].Son[1]; while(S[x].Son[0]) x=S[x].Son[0]; S[x].Son[0]=u,S[u].Fa=x,Splay(u); } void DeleteVal(int x) { x=FindKth(Root,x),Splay(x); int l=S[x].Son[0]; int r=S[x].Son[1]; S[x].Son[0]=S[x].Son[1]=0; S[l].Fa=S[r].Fa=0; Root=MergeTrees(l,r); } void ChangeVal(int x,int w) { x=FindKth(Root,x); ChangeNode(x,w),Splay(x); } unsigned long long Ask(int x,int y,int k) { int a=0,b=0,c=0,d=0; unsigned long long res=0; SplitTree(Root,x-1,a,b); SplitTree(b,y-x+1,c,d); res=S[c].Ans[k]; b=MergeTrees(c,d); Root=MergeTrees(a,b); return res; } int main() { int n=0,m=0; n=rdin(),Csh(); for(int i=1;i<=n;i++) Num[i]=rdin(); Num[0]=-INF,Num[n+1]=-INF; Root=BuildTree(0,n+1); m=rdin(); for(int i=1;i<=m;i++) { char opt=getchar(); while(opt!='I'&&opt!='D'&&opt!='R'&&opt!='Q') opt=getchar(); if(opt=='I') { int x=rdin(),y=rdin(); InsertVal(x+2,y); } if(opt=='D') { int x=rdin(); DeleteVal(x+2); } if(opt=='R') { int x=rdin(),y=rdin(); ChangeVal(x+2,y); } if(opt=='Q') { int l=rdin(),r=rdin(),k=rdin(); printf("%llu ",Ask(l+2,r+2,k)); } } return 0; }