记录编号	173986	评测结果	AAAAAAAAEE
题目名称	magictree	最终得分	80
用户昵称	一個人的雨	是否通过	未通过
代码语言	C++	运行时间	0.847 s
提交时间	2015-07-30 21:41:45	内存使用	38.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#define SpeedUp ios::sync_with_stdio(false)
using namespace std;
struct TREE{
	long long sum;
	int l;
	int r;
	long long delta;
	TREE *lc,*rc;
	TREE():sum(0),delta(0){}
};
int n,m;
long long a[5000888];

void update(TREE *p)
{
	p->lc->sum+=p->delta*(p->lc->r-p->lc->l);
	p->rc->sum+=p->delta*(p->rc->r-p->rc->l);
	p->lc->delta+=p->delta;
	p->rc->delta+=p->delta;
	p->delta=0;
}

void build(TREE *p,int l,int r){
	p->l=l;
	p->r=r;
	if (l+1==r)
	{
		p->sum=a[l];
		p->lc=NULL;
		p->rc=NULL;
		return;
	}
	else if (l+1<r)
	{
		p->lc=new TREE;
		p->rc=new TREE;
		build(p->lc,l,(l+r)/2);
		build(p->rc,(l+r)/2,r);
		p->sum=p->lc->sum+p->rc->sum;
		return;
	}
	return;
}

void change(TREE *p,int l,int r,long long delta){
	if (l<=p->l&&p->r<=r)
	{
		p->sum+=delta*(p->r-p->l);
		p->delta+=delta;
	}
	else
	{
		if (p->delta!=0)
			update(p);
		if (l<(p->l+p->r)/2)
		 change(p->lc,l,r,delta);
		if (r>(p->l+p->r)/2)
		 change(p->rc,l,r,delta);
		p->sum=p->lc->sum+p->rc->sum;
	}
}


long long  Q(TREE *p,int l,int r){
	if (l<=p->l&&p->r<=r) return p->sum;
	else
	{
		if (p->delta!=0)
			update(p);
		long long  ans=0;
		if (l<(p->l+p->r)/2)
			ans+=Q(p->lc,l,r);
		if (r>(p->l+p->r)/2)
			ans+=Q(p->rc,l,r);
		return ans;
	}
}

int main()
{
	freopen("magictree.in","r",stdin);
	freopen("magictree.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&m);
	int x,y,z;
	TREE *root=new TREE;
	for (int i=0;i<n;++i)
	 scanf("%d",&a[i]);
	build(root,0,n);
	for (int i=1;i<=m;++i)
	{
		char op;
		int x,y,z;
		getchar();
		cin>>op;
		if(op=='C')
		{
			scanf("%d%d%d",&y,&z,&x);
			change(root,y,z+1,x);
		}
		else if (op=='Q')
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",Q(root,x,y+1));
		}
	}
	return 0;
}