记录编号	305381	评测结果	AAAAAAAAWW
题目名称	magictree	最终得分	80
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.500 s
提交时间	2016-09-10 20:10:12	内存使用	55.19 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define LL long long
using namespace std;
namespace mine{
	inline int getint(){
		static int __c,__x;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline long long getll(){
		static int __c;
		static bool __neg;
		static long long __x;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10ll+(long long)(__c^48);
		if(__neg)return -__x;
		return __x;
	}
	inline void putint(int __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%10+48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
	inline void putll(long long __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=(int)(__x%10ll+48ll);
			__x/=10ll;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
const int maxn=2000010;
void build(int,int,int);
void madd(int,int,int);
void qsum(int,int,int);
void pushdown(int,int,int,int);
int sm[maxn<<2],lazy[maxn<<2]={0};
int n,m,s,t;
LL d,ans;
char c;
int main(){
#define MINE
#ifdef MINE
	freopen("magictree.in","r",stdin);
	freopen("magictree.out","w",stdout);
#endif
	n=getint();
	m=getint();
	build(1,n,1);
	while(m--){
		scanf(" %c",&c);
		s=getint()+1;
		t=getint()+1;
		if(c=='C'){
			d=getll();
			madd(1,n,1);
		}
		else if(c=='Q'){
			ans=0ll;
			qsum(1,n,1);
			putll(ans);
			putchar('\n');
		}
	}
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#else
	fclose(stdin);
	fclose(stdout);
#endif
	return 0;
}
void build(int l,int r,int rt){
	if(l==r){
		sm[rt]=getll();
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	sm[rt]=sm[rt<<1]+sm[rt<<1|1];
}
void madd(int l,int r,int rt){
	if(s<=l&&t>=r){
		sm[rt]+=(r-l+1)*d;
		lazy[rt]+=d;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	if(s<=mid)madd(l,mid,rt<<1);
	if(t>mid)madd(mid+1,r,rt<<1|1);
	sm[rt]=sm[rt<<1]+sm[rt<<1|1];
}
void qsum(int l,int r,int rt){
	if(s<=l&&t>=r){
		ans+=sm[rt];
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,mid,rt);
	if(s<=mid)qsum(l,mid,rt<<1);
	if(t>mid)qsum(mid+1,r,rt<<1|1);
}
void pushdown(int l,int r,int mid,int rt){
	if(!lazy[rt]||l==r)return;
	int lc=rt<<1,rc=rt<<1|1;
	sm[lc]+=(LL)(mid-l+1)*lazy[rt];
	lazy[lc]+=lazy[rt];
	sm[rc]+=(LL)(r-mid)*lazy[rt];
	lazy[rc]+=lazy[rt];
	lazy[rt]=0ll;
}