记录编号	552430	评测结果	AAAAAAAAEE
题目名称	magictree	最终得分	80
用户昵称	fw	是否通过	未通过
代码语言	C++	运行时间	1.159 s
提交时间	2020-07-27 18:20:09	内存使用	120.47 MiB

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN =2000001;
ll a[MAXN];
int n,m;
struct Node {
	int l,r,lz;
	ll sum;
	Node () {
		l=r=sum=lz=0;
	}
}tree[4000001];
void pushup(ll i) {
	tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
	return;
}
void pushdown(ll i) {
	if (tree[i].lz) {
		tree[i<<1].lz+=tree[i].lz;
		tree[i<<1|1].lz+=tree[i].lz;
		tree[i<<1].sum+=tree[i].lz*(tree[i<<1].r-tree[i<<1].l+1);
		tree[i<<1|1].sum+=tree[i].lz*(tree[i<<1|1].r-tree[i<<1|1].l+1);
		tree[i].lz=0;
	}
	return ;
}
void build (ll i,int l,int r) {
	tree[i].l=l;
	tree[i].r=r;
	if (r==l) {
		tree[i].sum=a[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	pushup(i);
	return;
}
ll search(ll i,int l,int r) {
	if (tree[i].l>=l&&tree[i].r<=r) {
		return tree[i].sum;
	}
	pushdown(i);
	if (tree[i].l>r||tree[i].r<l) return 0;
	ll s=0;
	if (tree[i<<1].r>=l) s+=search(i<<1,l,r);
	if (tree[i<<1|1].l<=r) s+=search(i<<1|1,l,r);
	return s;
}
void add (ll i,int l,int r,ll k) {
	if (tree[i].l>=l&&tree[i].r<=r) {
		tree[i].sum+=k*(tree[i].r-tree[i].l+1);
		tree[i].lz+=k;
		return ;
	}
	if (tree[i].l>r||tree[i].r<l) return ;
	pushdown(i);
	if (tree[i<<1].r>=l) add(i<<1,l,r,k);
	if (tree[i<<1|1].l<=r) add(i<<1|1,l,r,k);
	pushup(i);
	return; 
}
int main () {
	freopen("magictree.in","r",stdin);
	freopen("magictree.out","w",stdout);
	char c2;
	scanf("%d%d",&n,&m);
	for (int q=1;q<=n;q++) {
		scanf("%d",&a[q]);
	}
	build(1,1,n);
	int a,b,c;
	for (int q=1;q<=m;q++) {
		cin>>c2; 
		if (c2=='Q') {
			scanf("%d%d",&a,&b);
			printf("%lld\n",search(1,a+1,b+1));
		}
		if (c2=='C') {
			scanf("%d%d%d",&a,&b,&c);
			add(1,a+1,b+1,c);
		}
	}
	return 0;
}