wrong answer on about 27, and i don’t know why.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 10;
const int M = 15;
#define pc putchar
#define gc getchar
#define mp make_pair
#define pb push_back
#define int long long
template
inline void read(T &ret) {
ret = 0; char ch = gc(); int f = 1;
while (!isdigit(ch) && ch^’-’) ch = gc();
if (ch==’-’) f = -1, ch = gc();
while (isdigit(ch)) {
ret = (ret<<1) + (ret<<3) + (ch^48);
ch = gc();
} ret *= f; return ;
}
template
inline T qpow(T bas, T pw, T Md) {
T mult = 1;
while (pw) {
if (pw&1) mult = mult * bas % Md;
bas = bas * bas % Md;
pw >>= 1;
} return mult;
}
inline void fp() {
freopen(".in", “r”, stdin);
freopen(".out", “w”, stdout); return ;
}
int n, Q, root, cnt, C[M][M];
int a[N], tmp[N], siz[N], chd[N][2];
int pri[N], res[N][M];
void pushup(int rt) {
siz[rt] = siz[chd[rt][0]] + siz[chd[rt][1]] + 1, tmp[0] = 1;
for (int i=1; i<=10; ++i)
tmp[i] = tmp[i-1] * (siz[chd[rt][0]] + 1);
for (int i=0; i<=10; ++i) {
res[rt][i] = (res[chd[rt][0]][i] + a[rt] * tmp[i]);
for (int j=0; j<=i; ++j) res[rt][i] += C[i][j] * tmp[i-j] * res[chd[rt][1]][j];
} return ;
}
int newnod(int x) {
a[++cnt] = x, siz[cnt] = 1;
pri[cnt] = rand(), chd[cnt][0] = chd[cnt][1] = 0;
for (int i=0; i<=10; ++i) res[cnt][i] = x;
return cnt;
}
void split(int rt, int pos, int &x, int &y) {
if (!rt) x = y = 0;
else {
if (pos<=siz[chd[rt][0]])
y = rt, split(chd[rt][0], pos, x, chd[rt][0]);
else x = rt, split(chd[rt][1], pos-siz[chd[rt][0]]-1, chd[rt][1], y);
pushup(rt);
}
}
int Merge(int x, int y) {
if (!x || !y) return x + y;
if (pri[x] < pri[y]) {
chd[x][1] = Merge(chd[x][1], y);
pushup(x); return x;
} else {
chd[y][0] = Merge(x, chd[y][0]);
pushup(y); return y;
}
}
signed main() {
srand(time(NULL)); read(n); C[0][0] = 1;
for (int i=1; i<=10; ++i) {
C[i][0] = 1;
for (int j=1; j<=i; ++j) C[i][j] = C[i-1][j] + C[i-1][j-1];
}
for (int i=1; i<=n; ++i) {
int x; read(x);
root = Merge(root, newnod(x));
}
read(Q);
while (Q–) {
char opt[2]; scanf("%s", opt);
int L, R, val, x, y, z; read(L);
if (opt[0] == ‘I’) {
read(val); split(root, L, x, y);
root = Merge(Merge(x, newnod(val)), y);
} else if (opt[0] == ‘D’) {
split(root, L, x, y);
split(y, 1, y, z); root = Merge(x, z);
} else if (opt[0] == ‘R’) {
read(val); split(root, L, x, y);
split(y, 1, y, z), a[y] = val;
pushup(y); root = Merge(Merge(x, y), z);
} else if (opt[0] == ‘Q’) {
read®, read(val);
split(root, L, x, y), split(y, R-L+1, y, z);
printf("%lld\n", res[y][val]);
root = Merge(Merge(x, y), z);
}
}
return 0;
}