记录编号	393905	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	新史「新幻想史 -现代史-」	最终得分	100
用户昵称	Marvolo	是否通过	通过
代码语言	C++	运行时间	5.422 s
提交时间	2017-04-12 14:03:49	内存使用	20.92 MiB

#pragma GCC optimize(3)
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 100010
typedef long long LL;
using namespace std;

int i,n,m,j,cnt,Cnt;
char c;
int q[N],v[N];
LL ans[N],d[N];

struct Marvolo{
	int sign,x,y,z,t,id;
}a[N],b[N];

struct Tree{
	int l,r;
	LL d,p;
}t[6*N];

inline void Maketree(int x,int low,int high){
	int mid=(low+high)>>1;
	t[x].l=low;	t[x].r=high;
	if (low==high) return;
	Maketree(x*2,low,mid);	Maketree(x*2+1,mid+1,high);
}

inline void Clear(int X){
	int l=X*2,r=X*2+1;
	t[l].d+=1ll*t[X].p*(t[l].r-t[l].l+1);	t[r].d+=1ll*t[X].p*(t[r].r-t[r].l+1);
	t[l].p+=t[X].p;	t[r].p+=t[X].p;
	t[X].p=0;
}

inline void Add(int x,int low,int high,LL val){
	int mid=(t[x].l+t[x].r)>>1;
	if (t[x].l==t[x].r)	{t[x].d+=val;	return;}
	if (t[x].l==low&&t[x].r==high){
		t[x].d+=val*(t[x].r-t[x].l+1);	t[x].p+=val;	return;}
	if (t[x].p)	Clear(x);
	if (high<=mid)	Add(x*2,low,high,val);	else
	if (low>mid)	Add(x*2+1,low,high,val);	else{
		Add(x*2,low,mid,val);	Add(x*2+1,mid+1,high,val);
	}
	t[x].d=t[x*2].d+t[x*2+1].d;
}

inline LL Query(int x,int low,int high){
	int mid=(t[x].l+t[x].r)>>1;
	if (t[x].l==t[x].r)	return t[x].d;
	if (t[x].p)	Clear(x);
	if (low==t[x].l&&high==t[x].r)	return t[x].d;
	if (high<=mid)	return Query(x<<1,low,high);	else
	if (low>mid)	return Query((x<<1)+1,low,high);	else
	return Query(x<<1,low,mid)+Query((x<<1)+1,mid+1,high);
}

inline void CDQ(int L,int R,int l,int r){
	int mid=(l+r)>>1,i=0,tmp1=L,tmp2=L;
	if (L>R)	return;
	if (l==r){
		for (i=L;i<=R;i++)
		if (a[i].sign==1) Add(1,a[i].x,a[i].y,a[i].z);
		else ans[a[i].id]+=Query(1,a[i].x,a[i].y);
		for (i=L;i<=R;i++)
		if (a[i].sign==1)	Add(1,a[i].x,a[i].y,-a[i].z);
		return;
	}
	for (i=L;i<=R;i++)
		if (a[i].sign==1){
			if (a[i].t<=mid)	{
				Add(1,a[i].x,a[i].y,a[i].z);	++tmp2;
			}
		}	else {
			if (a[i].t>mid)	ans[a[i].id]+=Query(1,a[i].x,a[i].y);
			else tmp2++;
		}
	for (i=L;i<=R;i++)	if (a[i].sign==1&&a[i].t<=mid)	Add(1,a[i].x,a[i].y,-a[i].z);
	for (i=L;i<=R;i++)
	if (a[i].t<=mid)	b[tmp1++]=a[i];	else b[tmp2++]=a[i];
	for (i=L;i<=R;i++)	a[i]=b[i];
	CDQ(L,tmp1-1,l,mid);	CDQ(tmp1,R,mid+1,r);
}

int main(){
	freopen("cdcq_a.in","r",stdin);
	freopen("cdcq_a.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)	scanf("%lld",&d[i]);
	for (i=1;i<=m;i++){
		c=getchar();
		while (c!='Q'&&c!='M')	c=getchar();
		if (c=='Q')	{
			cnt++;
			a[cnt].sign=2;	scanf("%d%d%d",&a[cnt].x,&a[cnt].y,&a[cnt].t);
			a[cnt].id=++Cnt;
		}	else {
			cnt++;	a[cnt].sign=a[cnt+1].sign=1;
			scanf("%d%d%d",&a[cnt].x,&a[cnt].y,&a[cnt].z);
			a[cnt].z*=-1;	cnt++;	
			scanf("%d%d%d",&a[cnt].x,&a[cnt].y,&a[cnt].z);
			scanf("%d",&a[cnt].t);	a[cnt-1].t=a[cnt].t;
		}
	}
	Maketree(1,1,n);	CDQ(1,cnt,0,m);
	for (i=1;i<=n;i++)	Add(1,i,i,d[i]);
	for (i=1;i<=cnt;i++)	if (a[i].sign==2)	ans[a[i].id]+=Query(1,a[i].x,a[i].y);
	for (i=1;i<=Cnt;i++)	printf("%lld\n",ans[i]);
	return 0;
}