10 5

1 2 3 4 5 6 7 8 9 10

Q 4 4

Q 1 10

Q 2 4

C 3 6 3

Q 2 4

4

55

9

15

这题应该算是线段树区间入目题目，只是还能够用Splay来做，用Splay来维护序列。用到了平衡二叉树的一个重要的性质那就是中序遍历是有序的。人生第一道Splay（感人TAT。QAQ）

代码例如以下：

/*************************************************************************

    > File Name: Spaly.cpp

    > Author: acvcla

    > QQ:

    > Mail: acvcla@gmail.com

    > Created Time: 2014年11月16日 星期日 00时14分26秒

 ************************************************************************/

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<vector>

#include<cstring>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<cstdlib>

#include<ctime>

#include<set>

#include<math.h>

using namespace std;

typedef long long LL;

const int maxn = 1e5 + 100;

#define rep(i,a,b) for(int i=(a);i<=(b);i++)

#define pb push_back

LL add[maxn],sum[maxn];

int ch[maxn][2],siz[maxn],key[maxn],pre[maxn],A[maxn];

int root,tot;

void newnode(int &x,int fa,int Key)//新建节点

{

	x=++tot;

	pre[x]=fa;

	siz[x]=1;

	key[x]=sum[x]=Key;

	ch[x][0]=ch[x][1]=add[x]=0;

}

void Modify(int x,int val){//区间更新

	if(!x)return;

	add[x]+=val;

	key[x]+=val;

	sum[x]+=(LL)val*siz[x];

}

void push_down(int x){//下传标记

	if(!add[x])return ;

	Modify(ch[x][0],add[x]);

	Modify(ch[x][1],add[x]);

	add[x]=0;

}

void push_up(int x){//更新节点

	siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;

	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x];

}

void built(int &x,int L,int R,int fa){

	if(L>R)return;

	int M=(L+R)>>1;

	newnode(x,fa,A[M]);

	built(ch[x][0],L,M-1,x);

	built(ch[x][1],M+1,R,x);

	push_up(x);

}

void Init(int n)//初始化Spaly。加入了两个虚拟节点。便于提取区间，避免讨论

{

	root=tot=0;

	newnode(root,0,0);

	newnode(ch[root][1],root,0);

	for(int i=1;i<=n;i++)scanf("%d",A+i);

	built(ch[ch[root][1]][0],1,n,ch[root][1]);

	push_up(ch[root][1]);

	push_up(root);

}

void print(int x){

	if(!x)return;

	print(ch[x][0]);

	printf("%d ",key[x]);

	print(ch[x][1]);

}

void Rotate(int x,bool kind){//旋转，true右旋，false左旋

	int y=pre[x];

	push_down(y);//下传标记

	push_down(x);

	ch[y][!kind]=ch[x][kind];

	pre[ch[x][kind]]=y;

	ch[x][kind]=y;

	if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;//若y的父节点存在将其孩子指针指向x

	pre[x]=pre[y];

	pre[y]=x;

	push_up(y);//更新回来，须要注意的是。要先更新孩子

	push_up(x);

}

void Spaly(int x,int goal){//伸展操作。将x旋转到goal以下

	push_down(x);

	while(pre[x]!=goal){

		if(pre[pre[x]]==goal)Rotate(x,ch[pre[x]][0]==x);

		else{

			int y=pre[x];

			bool kind=(ch[pre[y]][0]==y);

			if(ch[y][kind]==x){

				Rotate(x,!kind);

				Rotate(x,kind);

			}else{

				Rotate(y,kind);

				Rotate(x,kind);

			}

		}

	}

	push_up(x);

	if(goal==0)root=x;//假设goal是0说明已经将x旋转到了根，所以要更新root

}

int Get_kth(int x,int k){//序列中的第k个值

	int t=siz[ch[x][0]]+1;

	if(t==k)return x;

	if(t>k)return Get_kth(ch[x][0],k);

	return Get_kth(ch[x][1],k-t);

}

int main(){

		ios_base::sync_with_stdio(false);

		cin.tie(0);

		siz[0]=sum[0]=0;//不存在的节点初始化为0避免讨论

		int n,q,l,r,x;

		scanf("%d%d",&n,&q);

		Init(n);

		char cmd[5];

		while(q--){

			scanf("%s%d%d",cmd,&l,&r);

			Spaly(Get_kth(root,l),0);

			Spaly(Get_kth(root,r+2),root);

			if(cmd[0]=='Q'){

				printf("%lld\n",sum[ch[ch[root][1]][0]]);

			}else{

				int Add;

				scanf("%d",&Add);

				Modify(ch[ch[root][1]][0],Add);

				push_up(ch[root][1]);

				push_up(root);

			}

		}

		return 0;

}