记录编号	414555	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]简单的求和问题	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	1.542 s
提交时间	2017-06-14 16:16:43	内存使用	43.98 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005,B=466,maxb=217;
long long b[maxb],sm[maxn],lazy[maxb];
short w[maxb][maxn];
int n,m,cntb,a[maxn],l[maxn],r[maxn],id[maxn],L[maxb],R[maxb];
int main(){
	freopen("get_sum.in","r",stdin);
	freopen("get_sum.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sm[i]=sm[i-1]+a[i];
		id[i]=(i-1)/B+1;
		if(!L[id[i]])L[id[i]]=i;
		R[id[i]]=i;
		cntb=id[i];
	}
	for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
	for(int k=1;k<=cntb;k++){
		for(int i=L[k];i<=R[k];i++){
			w[k][l[i]]++;
			w[k][r[i]+1]--;
			b[k]+=sm[r[i]]-sm[l[i]-1];
		}
		for(int i=1;i<=n;i++)w[k][i]+=w[k][i-1];
	}
	while(m--){
		char c;
		scanf(" %c",&c);
		if(c=='M'){
			int x,d;
			scanf("%d%d",&x,&d);
			d-=a[x];
			a[x]+=d;
			for(int i=1;i<=cntb;i++)b[i]+=w[i][x]*d;
			if(R[id[x]]-x+1>(B>>1)){
				lazy[id[x]]+=d;
				for(int i=L[id[x]];i<x;i++)sm[i]-=d;
			}
			else for(int i=R[id[x]];i>=x;i--)sm[i]+=d;
			for(x=id[x]+1;x<=cntb;x++)lazy[x]+=d;
		}
		else{
			int s,t;
			scanf("%d%d",&s,&t);
			long long ans=0;
			if(id[s]==id[t])for(int i=s;i<=t;i++)ans+=(sm[r[i]]+lazy[id[r[i]]])-(sm[l[i]-1]+lazy[id[l[i]-1]]);
			else{
				if(R[id[s]]-s+1>(B>>1)){
					ans+=b[id[s]];
					for(int i=L[id[s]];i<s;i++)ans-=(sm[r[i]]+lazy[id[r[i]]])-(sm[l[i]-1]+lazy[id[l[i]-1]]);
				}
				else for(int i=R[id[s]];i>=s;i--)ans+=(sm[r[i]]+lazy[id[r[i]]])-(sm[l[i]-1]+lazy[id[l[i]-1]]);
				if(t-L[id[t]]+1>(B>>1)){
					ans+=b[id[t]];
					for(int i=R[id[t]];i>t;i--)ans-=(sm[r[i]]+lazy[id[r[i]]])-(sm[l[i]-1]+lazy[id[l[i]-1]]);
				}
				else for(int i=L[id[t]];i<=t;i++)ans+=(sm[r[i]]+lazy[id[r[i]]])-(sm[l[i]-1]+lazy[id[l[i]-1]]);
				for(int i=id[s]+1;i<id[t];i++)ans+=b[i];
			}
			printf("%lld\n",ans);
		}
	}
	return 0;
}