记录编号	166372	评测结果	AAAAAAAAAA
题目名称	数列操作C	最终得分	100
用户昵称	<蒟蒻>我要喝豆奶	是否通过	通过
代码语言	C++	运行时间	0.854 s
提交时间	2015-06-15 09:28:20	内存使用	7.94 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#define SpeedUp while(1)
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[1000000];

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("shuliec.in","r",stdin);
	freopen("shuliec.out","w",stdout);
	//SpeedUp;
	cin>>n;
	int x,y,z;
	TREE *root=new TREE;
	for (int i=1;i<=n;++i)
	{
	 cin>>a[i];
    }
	build(root,1,n+1);
	cin>>m;
	for (int i=1;i<=m;++i)
	{
		char op[8];
		long long x,y,z;
		cin>>op;
		if(op[0]=='A')
		{
			cin>>y>>z>>x;
			change(root,y,z+1,x);
		}
		else if (op[0]=='S')
		{
			cin>>x>>y;
			cout<<Q(root,x,y+1)<<endl;
		}
	}
	return 0;
}