Description

设计一种数据结构，支持在一个序列中进行以下两种操作：

C l r k:将序列中第l到第r个数每个加上k。

Q l r:输出当前序列中第l到第r个数的总和

不能用线段树来解，不能用线段树来解，不能用线段树来解！

Input

第一行n,q(1 ≤ n,q ≤ 100000)，表示序列中数的个数和操作的个数。

第二行n个数，表示初始序列（-1000000000 ≤ 每个数≤ 1000000000）

第3至2+q行，每行一个操作，意义如题目描述所示。

Output

对于每个Q操作，输出对应的结果，每个一行。

Sample Input

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

Sample Output

4

55

9

15

代码求调

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,tot,rt,data[N];
char op[10];
struct Node{int ch[2],fa,siz,id,val,sum,lzy;}tree[N];
void pushup(int u){
	tree[u].siz=tree[tree[u].ch[0]].siz+tree[tree[u].ch[1]].siz+1;
	tree[u].sum=tree[tree[u].ch[0]].sum+tree[tree[u].ch[1]].sum+tree[u].val;
}
void pushdown(int u){
	if(!tree[u].lzy) return;
	tree[tree[u].ch[0]].sum+=tree[tree[u].ch[0]].siz*tree[u].lzy;
	tree[tree[u].ch[0]].lzy+=tree[u].lzy;
	tree[tree[u].ch[0]].val+=tree[u].lzy;
	tree[tree[u].ch[1]].sum+=tree[tree[u].ch[1]].siz*tree[u].lzy;
	tree[tree[u].ch[1]].lzy+=tree[u].lzy;
	tree[tree[u].ch[1]].val+=tree[u].lzy;
	tree[u].lzy=0;
}
int create(int id,int fa){
	tree[++tot].fa=fa;
	tree[tot].val=data[id];
	tree[tot].id=id;
	return tot;
}
void build(int &u,int l,int r,int fa){
	if(l>r) return;
	int mid=l+r>>1;
	u=create(mid,fa);
	build(tree[u].ch[0],l,mid-1,u);
	build(tree[u].ch[1],mid+1,r,u);
	pushup(u);
}
bool check(int u){return u==tree[tree[u].fa].ch[1];}
void rotate(int u){
	int fa=tree[u].fa,ffa=tree[fa].fa,k=check(u),p=check(fa);
	tree[fa].ch[k]=tree[u].ch[!k],tree[tree[u].ch[!k]].fa=fa;
	tree[u].ch[!k]=fa,tree[fa].fa=u;
	tree[ffa].ch[p]=u,tree[u].fa=ffa;
	pushup(fa),pushup(u);
}
void splay(int u,int goal){
	while(tree[u].fa!=goal){
		int fa=tree[u].fa,ffa=tree[fa].fa;
		if(ffa!=goal) check(u)^check(fa)?rotate(u):rotate(fa);
		rotate(u);
	}
	if(!goal) rt=u;
}
int kth(int x){
	int u=rt;
	while(1){
		if(x<=tree[tree[u].ch[0]].siz) u=tree[u].ch[0];
		else if(x==tree[tree[u].ch[0]].siz+1)  return u;
		else x-=tree[tree[u].ch[0]].siz+1,u=tree[u].ch[1];
	}
}
int query(int l,int r){
	int x=kth(l-1),y=kth(r+1);
	splay(x,rt),splay(y,x);
	return tree[tree[y].ch[0]].sum;
}
void modify(int l,int r,int k){
	int x=kth(l-1),y=kth(r+1);
	splay(x,rt),splay(y,x);
	int u=tree[y].ch[0];
	tree[u].val+=k,tree[u].lzy+=k,tree[u].sum+=k*tree[u].siz;
	pushup(y),pushup(x);
}
//void dfs(int u){
//	if(!u) return;
//	dfs(tree[u].ch[0]);
//	printf("Node %d , id = %d , val = %d\n	lc = %d , rc = %d\n",u,tree[u].id,tree[u].val,tree[u].ch[0],tree[u].ch[1]);
//	dfs(tree[u].ch[1]);
//}
//void debug(){puts("dfs:"),printf("rt = %d\n",rt),dfs(rt);} 
int main(){
	scanf("%d%d",&n,&q);
	for(int i=2;i<=n+1;i++) scanf("%d",data+i);
	data[1]=data[n+2]=0;
	build(rt,1,n+2,0);
	for(int i=1,l,r,k;i<=q;i++){
		scanf("%s",op);
		if(op[0]=='Q') scanf("%d%d",&l,&r),l++,r++,printf("%d\n",query(l,r));		
		if(op[9]=='C') scanf("%d%d%d",&l,&r,&k),l++,r++,modify(l,r,k);
	}
	return 0;
}
/*
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
*/