2019-08-06 20:31:26

\begin{aligned}\sum_{i=l}^ra_i(i-l+1)^k&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i(i-l+1)^k\right)\\&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\big((mid-l+1)-(i-mid)\big)^k\right)\\&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}(i-mid)^{j}\right)\\&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}\sum_{i=mid+1}^ra_i(i-mid)^{j}\right)\\&=lans_k+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}rans_j\right)\end{aligned}

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
#define int unsigned int

int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}

const int N=200000+10,K=10+10;

int n,Q;
int C[K][K];

inline void init() {
srand(19260817);
for (re int i=C[0][0]=1;i<=10;++i)
for (re int j=C[i][0]=1;j<=i;++j)
C[i][j]=C[i-1][j]+C[i-1][j-1];
}

// fhq treap
int root,tot=0;
int ch[N][2],sz[N],val[N],rnd[N];
int ans[N][K],pw[K];

inline int newnode(int w) {
++tot;
sz[tot]=1,val[tot]=w,rnd[tot]=rand();
for (re int i=0;i<=10;++i) ans[tot][i]=w;
}
inline void pushup(int x) {
int ls=ch[x][0],rs=ch[x][1];
sz[x]=sz[ls]+sz[rs]+1;
for (re int i=pw[0]=1;i<=10;++i) pw[i]=pw[i-1]*(sz[ls]+1);
for (re int k=0;k<=10;++k) {
ans[x][k]=ans[ls][k]+val[x]*pw[k];
for (re int i=0;i<=k;++i) ans[x][k]+=C[k][i]*pw[k-i]*ans[rs][i];
}
}
inline void split(int o,int k,int& x,int& y) {
if (!o) { x=y=0; return; }
if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
pushup(o);
}
inline int merge(int A,int B) {
if (!A||!B) return A+B;
if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}

signed main() {
init();
while (Q--) {
char op[2]; scanf("%s",op);
int o,r,z;
if (op[0]=='I') {
split(root,p-1,o,r);
root=merge(merge(o,newnode(w)),r);
} else if (op[0]=='D') {
split(root,p-1,o,r),split(r,1,r,z);
root=merge(o,z);
} else if (op[0]=='R') {
split(root,p-1,o,r),split(r,1,r,z);
val[r]=w,pushup(r);
root=merge(merge(o,r),z);
} else {
}