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

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+10,SIZE=500,CNT=210;
int n,m,pre[N],a[N],blo[N],l[N],r[N];
int tag[CNT],L[CNT],R[CNT],cnt;
ll sum[CNT];
unsigned short k[CNT][N];
int getpre(int x){
	if (!x) return 0;
	return pre[x]+tag[blo[x]];
}
void add(int p,int d){
	int v=d;
	d=v-a[p];a[p]=v;
	for (int i=p;i<=R[blo[p]];i++) pre[i]+=d;
	for (int i=blo[p]+1;i<=cnt;i++) tag[i]+=d;
	for (int i=0;i<=cnt;i++) sum[i]+=d*k[i][p];
}
ll query(int x,int LL,int RR){
	LL=max(LL,L[x]);
	RR=min(RR,R[x]);
	if (LL==L[x]&&RR==R[x]) return sum[x]; 
	ll ans=0;
	for (int i=LL;i<=RR;i++) ans+=getpre(r[i])-getpre(l[i]-1);
	return ans;
}
ll query(int l,int r){
	ll ans=0;
	for (int i=blo[l];i<=blo[r];i++) ans+=query(i,l,r);
	return ans;
}
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]);
		pre[i]=a[i]+pre[i-1];
		blo[i]=i/SIZE;
	}
	for (int i=1;i<=n;i++){
		scanf("%d%d",&l[i],&r[i]);
		k[blo[i]][r[i]+1]--;
		k[blo[i]][l[i]]++;
		sum[blo[i]]+=pre[r[i]]-pre[l[i]-1];
	}
	cnt=n/SIZE;
	for (int i=0;i<=cnt;i++){
		L[i]=max(i*SIZE,1);
		R[i]=min((i+1)*SIZE-1,n);
		for (int j=1;j<=n;j++) k[i][j]+=k[i][j-1];
	}
	char s[5];int l,r;
	while (m--){
		scanf("%s%d%d",s,&l,&r);
		if (s[0]=='M') add(l,r);
			else printf("%lld\n",query(l,r));
	}
	return 0;
}