记录编号	298775	评测结果	AAAAAAAAAAAAAAAA
题目名称	数列操作A	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.945 s
提交时间	2016-08-22 19:20:55	内存使用	1.79 MiB

#include<cstdio>
const int N=100010;
int son[N][2],fa[N],sum[N],key[N],n,m;
void update(int x){
	sum[x]=sum[son[x][0]]+sum[son[x][1]]+key[x];
}
bool getc(int x){
	return x==son[fa[x]][1];
}
void rotate(int x){//将x旋转至其父节点 
	int y=fa[x];
	bool b=getc(x);
	fa[x]=fa[y];
	if (fa[x]!=-1) son[fa[x]][getc(y)]=x;
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	update(y);update(x);
}
void splay(int x){
	while (fa[x]!=-1)
		rotate(x);
}
int getsum(int l,int r){
	splay(l-1);
	splay(r+1);
	return sum[son[son[r+1][0]][1]];
}
void add(int x,int y){
	splay(x);
	key[x]+=y;sum[x]+=y;
}

int main()
{
	freopen("shulie.in","r",stdin);
	freopen("shulie.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&key[i]),sum[i]=key[i];
	for (int i=0;i<=n+1;i++)
		son[i][0]=son[i][1]=n+2;
	for (int i=n;i>=0;i--){
		son[i][1]=i+1;
		sum[i]+=sum[i+1];
		fa[i+1]=i;
	}
	fa[0]=-1;
	scanf("%d",&m);
	char s[10];int x,y;
	while (m--){
		scanf("%s%d%d",s,&x,&y);
		if (s[0]=='A') add(x,y);
			else printf("%d\n",getsum(x,y));
	}
	return 0;
}