记录编号	352076	评测结果	AAAAAAAAAA
题目名称	magictree	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	0.494 s
提交时间	2016-11-16 21:14:34	内存使用	122.36 MiB

#include<cstdio>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("magictree.in","r",stdin);freopen("magictree.out","w",stdout);chul();Cu;
using namespace std;
typedef long long ll;
const int maxn=2000010;
ll tree[maxn<<2],lazy[maxn<<2];
int s,t,n;
void build(int rt,int l,int r){
	if(l==r){
		scanf("%lld",&tree[rt]);
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void update(int rt,int l,int mid,int r){
	if(lazy[rt]==0)return;
	ll k=lazy[rt];
	lazy[rt]=0;
	tree[rt<<1]+=(mid-l+1)*k;
	tree[rt<<1|1]+=(r-mid)*k;
	lazy[rt<<1]+=k;
	lazy[rt<<1|1]+=k;
	return;
}
ll asks(int rt,int l,int r){
	if(s<=l&&t>=r)return tree[rt];
	int mid=(l+r)>>1;
	update(rt,l,mid,r);
	if(t<=mid)return asks(rt<<1,l,mid);
	else if(s>mid)return asks(rt<<1|1,mid+1,r);
	else return asks(rt<<1,l,mid)+asks(rt<<1|1,mid+1,r);
}
void ques(){
	scanf("%d%d",&s,&t);
	s++;t++;
	printf("%lld\n",asks(1,1,n));
}
void adds(int rt,int l,int r,ll q){
	if(s<=l&&t>=r){
		tree[rt]+=(r-l+1)*q;
		lazy[rt]+=q;
		return;
	}
	int mid=(l+r)>>1;
	update(rt,l,mid,r);
	if(s<=mid)adds(rt<<1,l,mid,q);
	if(t>mid)adds(rt<<1|1,mid+1,r,q);
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}	
void adds(){
	ll q;
	scanf("%d%d%lld",&s,&t,&q);
	s++;t++;
	adds(1,1,n,q);
}
void chul(){
	int m;
	scanf("%d%d",&n,&m);
	build(1,1,n);
	char c;
	for(int i=1;i<=m;i++){
		while(c=getchar(),c!='Q'&&c!='C');
		if(c=='Q')ques();
		else adds();
	}
}
int main(){
	Begin;
}