代码大部分都是从GSS6搬过来的，就pushup函数有变化

不知道为什么会超时QWQ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define ll long long
using namespace std;
const int N=2e5+10;
char s[5];
ll c[12][12],fac[12];
struct tree
{
	int tot,root;
	int fa[N],son[N][2];
	ll val[N],sum[N][12];
	int size[N];
	tree()
	{ 
		tot=2,root=1;
		size[1]=2,size[2]=1;
		son[1][1]=2,fa[2]=1;
	}
	inline int get(int p){ return (son[fa[p]][1]==p); }
	inline void pushup(int p)
	{
		size[p]=size[son[p][0]]+size[son[p][1]]+1;
		int add=size[son[p][0]]+1;
		fac[0]=1;
		for(int k=1;k<=10;k++)
			fac[k]=fac[k-1]*(ll)add;
		for(register int k=0;k<=10;k++)
		{
			sum[p][k]=sum[son[p][0]][k]+val[p]*fac[k];
			for(register int j=0;j<=k;j++)
				sum[p][k]+=sum[son[p][1]][j]*c[k][j]*fac[k-j];
		}
	}
	inline void rotate(int p)
	{
		int f=fa[p],r=get(p);
		if(fa[f]) son[fa[f]][get(f)]=p;
		fa[p]=fa[f];
		if(son[p][r^1]) fa[son[p][r^1]]=f;
		son[f][r]=son[p][r^1];
		son[p][r^1]=f,fa[f]=p;
		pushup(f),pushup(p);
	}
	inline void splay(int p)
	{
		while(fa[p])
		{
			if(fa[fa[p]]&&get(p)==get(fa[p])) rotate(fa[p]);
			rotate(p);
		}
	}
	inline int findval(int p,int rank)
	{
		if(rank<=size[son[p][0]]) return findval(son[p][0],rank);
		rank-=size[son[p][0]]+1;
		if(rank<=0) return p;
		else return findval(son[p][1],rank);
	}
	inline int merge(int p,int q)
	{
		if(p==0) return q;
		if(q==0) return p;
		while(son[p][1]) p=son[p][1];
		splay(p);
		son[p][1]=q,fa[q]=p;
		pushup(p);
		return p;
	}
	inline void split(int rt,int k,int &p,int &q)
	{
		p=findval(rt,k);  
		splay(p);
		q=son[p][1];
		son[p][1]=fa[q]=0;
		pushup(p);
	}
	inline void Insert(int rank,ll num)
	{
		int x,y,p=++tot;
		split(root,rank,x,y);
		son[x][1]=p,fa[p]=x;
		val[p]=num;
		pushup(p),pushup(x);
		root=merge(x,y);
	}
	inline void Delet(int rank)
	{
		int p=findval(root,rank);
		splay(p),root=p;
		int x=son[p][0],y=son[p][1];
		son[p][0]=son[p][1]=fa[x]=fa[y]=0;
		root=merge(x,y);
	}
	inline void Update(int rank,ll num)
	{
		int p=findval(root,rank);
		splay(p),root=p;
		val[p]=num,pushup(p);
	}
	inline ll Query(int l,int r,int k)
	{
		int lef,rt,p,rig; ll ans;
		split(root,l-1,lef,rt);
		split(rt,r-l+1,p,rig);
		ans=sum[p][k];
		rt=merge(p,rig);
		root=merge(lef,rt);
		return ans;
	}
}t;
int main()
{
	for(register int i=0;i<=10;i++)
	{
		c[i][0]=c[i][i]=1;
		for(register int j=1;j<i;j++)
			c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	int n,m,a,b,c; ll v;
	scanf("%d",&n);
	for(register int i=1;i<=n;i++)
	{
		scanf("%lld",&v);
		t.Insert(i,v);
	}
	scanf("%d",&m);
	for(register int i=1;i<=m;i++)
	{
		scanf("%s",s);
		if(s[0]=='I')
		{
			scanf("%d%lld",&a,&v); 
			a++,t.Insert(a,v);
		}
		if(s[0]=='D')
		{
			scanf("%d",&a);
			a+=2,t.Delet(a);	
		}
		if(s[0]=='R')
		{
			scanf("%d%lld",&a,&v);
			a+=2,t.Update(a,v);
		}
		if(s[0]=='Q')
		{
			scanf("%d%d%d",&a,&b,&c);
			a+=2,b+=2,printf("%lld\n",t.Query(a,b,c));
		}
	}
	return 0;
}