记录编号	393901	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	新史「新幻想史 -现代史-」	最终得分	100
用户昵称	fjzzq2002	是否通过	通过
代码语言	C++	运行时间	1.033 s
提交时间	2017-04-12 13:52:33	内存使用	8.35 MiB

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <limits>
#include <set>
#include <map>
using namespace std;
#define SZ 123456
typedef long long ll;
int n,m,Q=0,q=0; ll ans[SZ];
struct cq {int tp,t,qx,qy,id,wx,wy,v1,v2;}qs[SZ];
bool operator < (cq a,cq b) {return a.t<b.t;}
ll a1[SZ],a2[SZ];
ll qzh(int r)
{
    ll s1=0,s2=0;
    for(int i=r;i>=1;i-=i&-i) s1+=a1[i], s2+=a2[i];
    return (r+1)*s1-s2;
}
ll sum(int l,int r)
{
    return qzh(r)-qzh(l-1);
}
void edt(ll a,ll s1)
{
    ll s2=a*s1;
    for(;a<=n;a+=a&-a) a1[a]+=s1, a2[a]+=s2;
}
void edt(int l,int r,ll a) {edt(l,a); edt(r+1,-a);}
void cdq(int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    sort(qs+l,qs+mid+1);
    sort(qs+mid+1,qs+r+1);
    int cur=l;
    for(int i=mid+1;i<=r;i++)
    {
        if(qs[i].tp!=1) continue;
        int t=qs[i].t;
        while(cur<=mid&&qs[cur].t<=t)
        {
            if(qs[cur].tp==0)
            {
            	edt(qs[cur].qx,qs[cur].qy,-qs[cur].v1);
            	edt(qs[cur].wx,qs[cur].wy,qs[cur].v2);
			}
            ++cur;
        }
        ans[qs[i].id]+=sum(qs[i].qx,qs[i].qy);
    }
    for(int i=l;i<cur;i++) if(qs[i].tp==0)
    {
        edt(qs[i].qx,qs[i].qy,qs[i].v1);
        edt(qs[i].wx,qs[i].wy,-qs[i].v2);
	}
}
ll b2[SZ];
void edt2(int x,int y)
{
	for(;x<=n;x+=x&-x) b2[x]+=y;
}
ll sum2(int x)
{
	ll ans=0;
	for(;x>=1;x-=x&-x) ans+=b2[x];
	return ans;
}
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int aa,bb;int F(){
    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
}
#define gi F()
int main()
{
	freopen("cdcq_a.in","r",stdin);
	freopen("cdcq_a.out","w",stdout);
	n=gi,m=gi;
	for(int i=1;i<=n;i++) edt2(i,gi);
	for(int i=1;i<=m;i++)
	{
		char s=0;
		while(s!='Q'&&s!='M') s=getc();
		if(s=='Q')
		{
			int x=gi,y=gi,t=gi;
			++Q; ++q; qs[Q].id=q; qs[Q].tp=1;
			qs[Q].qx=x; qs[Q].qy=y; qs[Q].t=t;
			ans[q]=sum2(y)-sum2(x-1);
		}
		else
		{
			int x=gi,y=gi,z=gi,l=gi,r=gi,v=gi,t=gi;
			++Q; qs[Q].tp=0; qs[Q].qx=x; qs[Q].qy=y; qs[Q].v1=z;
			qs[Q].wx=l; qs[Q].wy=r; qs[Q].v2=v; qs[Q].t=t;
		}
	}
	cdq(1,Q);
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]); 
}