Description:

一个序列， $Q$ 次操作，插入，修改，删除，询问 $\begin{align}(\sum_{i=l}^{r}A[i]\times (i-l+1)^k\end{align}$ $mod$ $2^{32})$ 。

$1\le N \le 100000$ $0\le k \le 10$

Solution:

$k\le 10$ ，在 $splay$ 中维护十一个值 $d[0]$ ~ $d[10]$ ， $d[k]$ 表示 $\begin{align}\sum_{i=rt_l}^{rt_r}A[i]\times (i-rt_l+1)^k\end{align}$ 。 .左子树中的答案可以直接累加，根节点部分 $(i-l+1)^k=(siz_{lc}+1)^k$ ，求幂直接加即可。

右子树部分 $A[rc]\times (i-l+1)^k=A[rc]\times (siz_{lc}+1+siz_{(rc_{lc})}+1)^k$ 。

由二项式定理得

​ $A[rc]\times(siz_{lc}+1+siz_{(rc_{lc})}+1)^k$

$\begin{align}=A[rc]\times\sum_{i=0}^kC_k^i\times (siz_{lc}+1)^{k-i}\times (siz_{(rc_{lc})}+1)^i\end{align}$

$\begin{align}=\sum_{i=0}^kC_k^i\times(siz_{lc}+1)^{k-i}\times d_{rc}[i]\end{align}$

对于 $mod$ $2^{32}$ ， $unsigned$ $int$ 自然溢出即可。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

char getc()

{

	char c = getchar();

	while(c < 'A' || c > 'Z')c = getchar();

	return c;

}

int read()

{

	int res = 0,f;

	char c = getchar();

	while((c < '0' || c > '9') && c != '-')c = getchar();

	if(c == '-'){f = -1;c = getchar();}

	else{f = 1;}

	while('0' <= c && c <= '9')

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

#define MAXK 10

typedef unsigned int uint;

uint c[11][11];

void init()

{

	c[0][0] = 1;

	for(int i = 1;i <= MAXK;++i)

	{

		c[i][0] = 1;

		for(int j = 1;j <= i;++j)

		{

			c[i][j] = c[i - 1][j] + c[i - 1][j - 1];

		}

	}

	return;

}

int a[MAXN];

struct node

{

	int fa,c[2],siz;

	uint d[11],v;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void maintain(int rt)

{

	int lc = t[rt].c[0],rc = t[rt].c[1];

	t[rt].siz = t[lc].siz + t[rc].siz + 1;

	for(int k = 0;k <= MAXK;++k)t[rt].d[k] = t[lc].d[k];

	uint power = t[lc].siz + 1,cur = 1;

	for(int k = 0;k <= MAXK;++k,cur *= power)t[rt].d[k] += t[rt].v * cur;

	for(int k = 0;k <= MAXK;++k)

	{

		cur = 1;

		for(int i = k;i >= 0;--i,cur *= power)

		{

			t[rt].d[k] += c[k][i] * cur * t[rc].d[i];

		}

	}

	return;

}

void build(int &rt,int l,int r,int f)

{

	if(l > r)return;

	rt = newnode();

	int mid = ((l + r) >> 1);

	t[rt].v = (uint)a[mid];

	t[rt].fa = f;

	for(int i = 0;i <= MAXK;++i)t[rt].d[i] = (uint)a[mid];

	build(t[rt].c[0],l,mid - 1,rt);

	build(t[rt].c[1],mid + 1,r,rt);

	maintain(rt);

	return;

}

int id(int x){return (t[t[x].fa].c[0] == x ? 0 : 1);}

void connect(int x,int f,int p){t[x].fa = f;t[f].c[p] = x;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	connect(t[x].c[fx^1],y,fx);

	connect(y,x,fx^1);

	connect(x,z,fy);

	maintain(y);maintain(x);

	return;

}

void splay(int x,int &k)

{

	int to = t[k].fa;

	while(t[x].fa != to)

	{

		int y = t[x].fa;

		if(t[y].fa == to){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	k = x;

	return;

}

int find_kth(int k)

{

	int cur = root;

	while(true)

	{

		if(k <= t[t[cur].c[0]].siz)cur = t[cur].c[0];

		else if(k > t[t[cur].c[0]].siz + 1)

		{

			k -= t[t[cur].c[0]].siz + 1;

			cur = t[cur].c[1];

		}

		else

		{

			return cur;

		}

	}

}

void remove(int x)

{

	++x;

	splay(find_kth(x - 1),root);

	splay(find_kth(x + 1),t[root].c[1]);

	t[t[root].c[1]].c[0] = 0;

	maintain(t[root].c[1]);

	maintain(root);

	return;

}

void insert(int x,int v)

{

	++x;

	splay(find_kth(x - 1),root);

	splay(find_kth(x),t[root].c[1]);

	int k = newnode();

	t[k].v = (uint)v;

	for(int i = 0;i <= MAXK;++i)

	{

		t[k].d[i] = (uint)v;

	}

	connect(t[root].c[1],k,1);

	connect(k,root,1);

	maintain(k);maintain(root);

	return;

}

void change(int x,int v)

{

	++x;

	splay(find_kth(x),root);

	t[root].v = (uint)v;

	for(int i = 0;i <= MAXK;++i)

	{

		t[root].d[i] = (uint)v;

	}

	maintain(root);

	return;

}

uint query(int l,int r,int k)

{

	++l;++r;

	splay(find_kth(l - 1),root);

	splay(find_kth(r + 1),t[root].c[1]);

	return t[t[t[root].c[1]].c[0]].d[k];

}

int main()

{

	init();

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

	}

	build(root,0,n + 1,0);

	scanf("%d",&m);

	char c;int x,y,z;

	for(int i = 1;i <= m;++i)

	{

		c = getc();

		if(c == 'I')

		{

			x = read();y = read();

			++x;

			insert(x,y);

		}

		if(c == 'D')

		{

			x = read();

			++x;

			remove(x);

		}

		if(c == 'R')

		{

			x = read();y = read();

			++x;

			change(x,y);

		}

		if(c == 'Q')

		{

			x = read();y = read();z = read();

			++x,++y;

			printf("%u\n",query(x,y,z));

		}

	}

	return 0;

}