记录编号	264714	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015]简单的求和问题	最终得分	100
用户昵称	Aglove	是否通过	通过
代码语言	C++	运行时间	1.970 s
提交时间	2016-05-30 14:08:27	内存使用	12.14 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long LL;
const int maxn=100010;
int n,m,cnt,mblo,km;
int nblo,kn;
int a[maxn],b[maxn];
int pos[maxn];
int Num[maxn],add[maxn];
LL Sa[maxn],Sf[maxn];
struct OP{
	int L,R;
}c[maxn];
struct ASK{
	char type;
	int u,v,id;
}Q[maxn<<1],Q1[maxn<<1];
LL ans[maxn<<1];
bool cmpu(const ASK &A,const ASK &B){return A.u<B.u;}
void read(int &num){
	num=0;char ch=getchar();
	while(ch<'!')ch=getchar();
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void UPD(int u,int v){
	int L=pos[u],R=pos[v],tmp;
	if(L==R){
		for(int i=u;i<=v;++i)Num[i]++;
	}else{
		tmp=L*nblo;
		for(int i=u;i<=tmp;++i)Num[i]++;
		tmp=(R-1)*nblo+1;
		for(int i=tmp;i<=v;++i)Num[i]++;
		for(int i=L+1;i<R;++i)add[i]++;
	}return;
}
int ask(int u){return Num[u]+add[pos[u]];}

int main(){
	freopen("get_sum.in","r",stdin);
	freopen("get_sum.out","w",stdout);
	read(n);read(m);nblo=(int)(sqrt(n));
	for(int i=1;i<=n;++i)read(a[i]),b[i]=a[i],pos[i]=(i-1)/nblo+1;
	for(int i=1;i<=n;++i)read(c[i].L),read(c[i].R);
	for(int i=1;i<=m;++i){
		cnt++;Q[cnt].type=getchar();
		while(Q[cnt].type<'!')Q[cnt].type=getchar();
		Q[cnt].id=cnt;
		if(Q[cnt].type=='Q'){
			read(Q[cnt].u);Q[cnt].u--;
			cnt++;Q[cnt].type='Q';Q[cnt].id=cnt;
			read(Q[cnt].u);
		}else{
			read(Q[cnt].u);read(Q[cnt].v);
			Q[cnt].v=Q[cnt].v-b[Q[cnt].u];
			b[Q[cnt].u]+=Q[cnt].v;
		}
	}mblo=(int)(sqrt(cnt));
	km=(cnt%mblo==0?cnt/mblo:cnt/mblo+1);
	for(int i=1;i<=cnt;++i)Q1[i]=Q[i];
	sort(Q1+1,Q1+cnt+1,cmpu);
	int now=1;
	for(int i=1;i<=cnt;++i){
		if(Q1[i].type=='M')continue;
		while(now<=n&&now<=Q1[i].u){
			UPD(c[now].L,c[now].R);
			now++;
		}
		int cur=Q1[i].id;
		int pi=(cur-1)/mblo+1;
		int L=(pi-1)*mblo+1;
		for(int j=L;j<=cnt;++j){
			if(Q[j].id>cur)break;
			if(Q[j].type=='Q')continue;
			ans[cur]=ans[cur]+1LL*Q[j].v*ask(Q[j].u);
		}
	}
	for(int i=1;i<=n;++i)Sa[i]=Sa[i-1]+a[i];
	for(int i=1;i<=n;++i)Sf[i]=Sf[i-1]+Sa[c[i].R]-Sa[c[i].L-1];
	for(int i=1;i<=km;++i){
		int L=(i-1)*mblo+1,R=min(cnt,i*mblo);
		for(int j=L;j<=R;++j){
			if(Q[j].type=='M'){
				a[Q[j].u]+=Q[j].v;
			}else ans[Q[j].id]=ans[Q[j].id]+Sf[Q[j].u];
		}
		for(int j=1;j<=n;++j)Sa[j]=Sa[j-1]+a[j];
		for(int j=1;j<=n;++j)Sf[j]=Sf[j-1]+Sa[c[j].R]-Sa[c[j].L-1];
	}
	for(int i=1;i<=cnt;++i){
		if(Q[i].type=='Q'){
			printf("%lld\n",ans[i+1]-ans[i]);
			i++;
		}
	}return 0;
}