求助卡常（T on 27）

#include <bits/stdc++.h>

using namespace std;

typedef unsigned int ll;

#define int unsigned int

const int maxn = 2e5+50;
const int maxk = 15;
const int K = 10;

ll R()
{
    ll x = 0,f = 1;
    char c = getchar();
    while(c > '9' || c < '0')
    {
        if(c == '-')f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

#define ls(rt) t[rt].ls
#define rs(rt) t[rt].rs
#define siz(rt) t[rt].siz
#define val(rt) t[rt].val
#define reg register

ll tot,rot,a[maxn],p[maxk],C[maxk][maxk];
struct Tree{ ll ls,rs,siz,val,rval,ans[maxk]; }t[maxn];

inline void pushup(reg ll rt)
{
    siz(rt) = siz(ls(rt)) + siz(rs(rt)) + 1;
    p[0] = 1;
    for(reg int i = 1 ; i <= K ; i++)p[i] = p[i-1] * (siz(ls(rt)) + 1);
    for(reg int i = 0 ; i <= K ; i++)
    {
        t[rt].ans[i] = t[ls(rt)].ans[i] + val(rt) * p[i];
        for(reg int j = 0 ; j <= i ; j++)t[rt].ans[i] += C[i][j] * p[i-j] * t[rs(rt)].ans[j];
    }
}

mt19937 rd(time(0));

inline ll newnode(ll val)
{
    ++tot;
    t[tot].ls = t[tot].rs = 0;
    t[tot].siz = 1,t[tot].val = val,t[rot].rval = rd();
    for(reg int i = 0 ; i <= K ; i++)t[tot].ans[i] = val;
    return tot;
}

inline void split(ll rt,ll &x,ll &y,ll siz)
{
    if(!rt){ x = y = 0; return; }
    if(siz(ls(rt)) + 1 <= siz)
    {
        x = rt;
        split(rs(rt),rs(rt),y,siz-siz(ls(rt))-1);
    }
    else
    {
        y = rt;
        split(ls(rt),x,ls(rt),siz);
    }
    pushup(rt);
}

inline ll merge(ll x,ll y)
{
    if(!x || !y)return x + y;
    if(t[x].rval < t[y].rval)
    {
        rs(x) = merge(rs(x),y);
        pushup(x);
        return x;
    }
    else
    {
        ls(y) = merge(x,ls(y));
        pushup(y);
        return y;
    }
}

char s[2];

void Lei()
{
    C[0][0] = 1;
    for(reg int i = 1 ; i <= K ; i++)
    {
        C[i][0] = 1;
        for(reg int j = 1 ; j <= i ; j++)C[i][j] = C[i-1][j] + C[i-1][j-1];
    }
    ll n = R();
    for(reg int i = 1 ; i <= n ; i++)a[i] = R(),rot = merge(rot,newnode(a[i]));
    ll m = R(),pos,val,x,y,z;
    for(reg int i = 1 ; i <= m ; i++)
    {
        scanf("%s",s+1);
        if(s[1] == 'I')
        {
            pos = R(),val = R();
            split(rot,x,y,pos);
            x = merge(x,newnode(val));
            rot = merge(x,y);
        }
        else if(s[1] == 'D')
        {
            pos = R();
            split(rot,x,y,pos);
            split(y,y,z,1);
            rot = merge(x,z);
        }
        else if(s[1] == 'R')
        {
            pos = R(),val = R();
            split(rot,x,y,pos);
            split(y,y,z,1);
            x = merge(x,newnode(val));
            rot = merge(x,z);
        }
        else
        {
            ll l = R(),r = R()+1,k = R();
            split(rot,x,y,r);
            split(x,x,z,l);
            printf("%u\n",t[z].ans[k]);
            x = merge(x,z);
            rot = merge(x,y);
        }
    }   
}

signed main()
{
    Lei();
    return 0;
}