记录编号	173561	评测结果	AAAAAAAAAA
题目名称	magictree	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.276 s
提交时间	2015-07-29 09:58:23	内存使用	91.87 MiB

#include <cstdio>
#include <iostream>

#define MAXN 2000001
#define READ

using namespace std;

int n,m;
char inp[20];
long long tree[3*MAXN];
long long add[3*MAXN];

void Clear(int ,int );
void Build(int ,int ,int );
void Update(int ,int ,long long  ,int ,int ,int );
long long Query(int ,int ,int ,int ,int );
inline int in();
inline long long qin();

int main(){
	#ifdef READ
		freopen("magictree.in","r",stdin);
		freopen("magictree.out","w",stdout);
	#endif
	int i;
	n=in();
	m=in();
	if(n==0)
		return 0;
	Build(0,n-1,1);
	for(i=1;i<=m;++i){
		scanf("%s",inp);
		if(inp[0]=='Q'){
			int x,y;
			x=in();
			y=in();
			printf("%lld\n",Query(x,y,0,n-1,1));
		}
		if(inp[0]=='C'){
			int x,y;
			long long w;
			x=in();
			y=in();
			w=qin();
			Update(x,y,w,0,n-1,1);
		}
	}
} 

void Build(int l,int r,int rt){
	if(l==r){
		tree[rt]=qin();
		return ;
	}
	int mid=(l+r)>>1;
	int temp=rt<<1;
	Build(l,mid,temp);
	Build(mid+1,r,temp|1);
	tree[rt]=tree[temp]+tree[temp|1];
	return ;
}

void Clear(int rt,int len){
	if(add[rt]==0)
		return ;
	int temp=rt<<1;
	tree[temp]+=add[rt]*(len-(len>>1));
	tree[temp|1]+=add[rt]*(len>>1);
	add[temp]+=add[rt];
	add[temp|1]+=add[rt];
	add[rt]=0;
	return ;	
}

long long Query(int pos_l,int pos_r,int l,int r,int rt){
	if(pos_l<=l&&pos_r>=r)
		return tree[rt];
	Clear(rt,r-l+1);
	int mid=(l+r)>>1;
	int temp=rt<<1;
	long long Sum=0;
	if(pos_l<=mid)
		Sum=Query(pos_l,pos_r,l,mid,temp);
	if(pos_r>mid)
		Sum+=Query(pos_l,pos_r,mid+1,r,temp|1);
	tree[rt]=tree[temp]+tree[temp|1];	
	return Sum;		
}

void Update(int pos_l,int pos_r,long long new_date,int l,int r,int rt){
	if(pos_l<=l&&pos_r>=r){
		tree[rt]+=new_date*(r-l+1);
		add[rt]+=new_date;
		return ;
	}
	Clear(rt,r-l+1);
	int mid=(l+r)>>1;
	int temp=rt<<1;
	if(pos_l<=mid)
		Update(pos_l,pos_r,new_date,l,mid,temp);
	if(pos_r>mid)
		Update(pos_l,pos_r,new_date,mid+1,r,temp|1);
	tree[rt]=tree[temp]+tree[temp|1];
	return ;		
}

inline long long qin(){
	long long temp=0;char c=getchar();bool flag=0;
	while(c<'0'||c>'9'){
		if(c=='-'){
			flag=1;
		}
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()){
		temp=temp*10+c-48;
	}
	if(flag) return -temp;
	return temp;
}

inline int in(){
	int temp=0;char c=getchar();bool flag=0;
	while(c<'0'||c>'9'){
		if(c=='-'){
			flag=1;
		}
		c=getchar();
	}
	for(;c>='0'&&c<='9';c=getchar()){
		temp=temp*10+c-48;
	}
	if(flag) return -temp;
	return temp;
}