记录编号	422614	评测结果	AAAAATTTTT
题目名称	[HZOI 2015]简单的求和问题	最终得分	50
用户昵称	Hzoi_Maple	是否通过	未通过
代码语言	C++	运行时间	11.813 s
提交时间	2017-07-10 06:59:31	内存使用	3.37 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
int n,m,x,y,blo,bl[100001],a[100001],l[100001],r[100001];
ll w[100001],sum[1001],gg[100001];
int read(){
	int sum=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum;
}
inline int lowbit(int i){
	return i&(-i);
}
void update(int x,int y){
	while(x<=n){
		w[x]+=y;
		x+=lowbit(x);
	}
}
ll gsum(int x){
	ll ans=0;
	while(x>0){
		ans+=w[x];
		x-=lowbit(x);
	}
	return ans;
}
inline ll query(int x,int y){
	return gsum(y)-gsum(x-1);
}
void change(int x,int y){
	for(int i=1;i<=n;++i)
		if(x>=l[i]&&x<=r[i]){
			sum[bl[i]]+=y-a[x];
			gg[i]+=y-a[x];	
		}
	a[x]=y;
} 
ll ask(int x,int y){
	ll ans=0;
	for(int i=x;i<=min(bl[x]*blo,y);++i)
		ans+=gg[i];
	if(bl[x]!=bl[y])
		for(int i=(bl[y]-1)*blo+1;i<=y;++i)
			ans+=gg[i];
	for(int i=bl[x]+1;i<=bl[y]-1;++i)
		ans+=sum[i];
	return ans;
}
int main(){
	freopen("get_sum.in","r",stdin);
	freopen("get_sum.out","w",stdout);
	n=read();m=read();
	blo=(int)sqrt(n+0.5);
	for(int i=1;i<=n;++i){
		a[i]=read();
		bl[i]=(i-1)/blo+1;
		update(i,a[i]);
	}
	for(int i=1;i<=n;++i){
		l[i]=read();r[i]=read();
		gg[i]=query(l[i],r[i]);
		sum[bl[i]]+=gg[i];
	}
	char s[2];
	for(int i=1;i<=m;++i){
		scanf("%s",s);
		x=read();y=read();
		if(s[0]=='M')
			change(x,y);
		else
			printf("%lld\n",ask(x,y));
	}
	return 0;
}