记录编号	205727	评测结果	AAAAAAAAAA
题目名称	magictree	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.797 s
提交时间	2015-11-05 17:47:02	内存使用	91.84 MiB

#include<cstdio>
#define LL long long
#define maxn 2000010
using namespace std;
LL sum[maxn*3],add[maxn*3];
int n,m;
char c[5];
inline LL init(){
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	LL x=0;
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
	return x;
}
inline int in(){
	char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	int x=0;
	for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-48;
	return x;
}
void push_down(int rt,int len){
	if(!add[rt]) return;
	add[rt<<1]+=add[rt];add[rt<<1|1]+=add[rt];
	sum[rt<<1]+=(LL)add[rt]*(len-(len>>1));
	sum[rt<<1|1]+=(LL)add[rt]*(len>>1);
	add[rt]=0;
}
void Build(int x,int y,int rt){
	add[rt]=0;
	if(x==y){
		sum[rt]=init();
		return;
	}
	int mid=(x+y)>>1;
	Build(x,mid,rt<<1);
	Build(mid+1,y,rt<<1|1);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int l,int r,LL w,int x,int y,int rt){
	if(l<=x&&r>=y){
		sum[rt]+=(LL)w*(y-x+1);add[rt]+=w;return;
	}
	push_down(rt,y-x+1);
	int mid=(x+y)>>1;
	if(l<=mid) update(l,r,w,x,mid,rt<<1);
	if(r>mid) update(l,r,w,mid+1,y,rt<<1|1);
	sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
LL Que(int l,int r,int x,int y,int rt){
	if(l<=x&&r>=y) return sum[rt];
	push_down(rt,y-x+1);
	int mid=(x+y)>>1;
	LL wa=0;
	if(l<=mid) wa+=Que(l,r,x,mid,rt<<1);
	if(r>mid) wa+=Que(l,r,mid+1,y,rt<<1|1);
	return wa;
}
int main(){
    freopen("magictree.in","r",stdin);
	freopen("magictree.out","w",stdout);
    n=in();m=in();
	Build(0,n-1,1);
	for(int i=1;i<=m;++i){
	   scanf("%s",c);
	   int x,y;
	   LL z;
	   if(c[0]=='Q'){
		  x=in();y=in();
		  printf("%lld\n",Que(x,y,0,n-1,1));
	   }
	   else{
			x=in();y=in();z=init();
			update(x,y,z,0,n-1,1);
	   }
	}
	//getchar();getchar();
	return 0;
}