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

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+10;
ll sum[N],tag[N];
#define lc x<<1
#define rc x<<1|1
void modify(int x,int l,int r,ll d){
	tag[x]+=d;
	sum[x]+=d*(r-l+1);
}
void pushdown(int x,int l,int r){
	if (l!=r&&tag[x]){
		int mid=(l+r)>>1;
		modify(lc,l,mid,tag[x]);
		modify(rc,mid+1,r,tag[x]);
		tag[x]=0;
	}
}
void add(int x,int l,int r,int L,int R,int d){
	if (l>=L&&r<=R) return modify(x,l,r,d);
	pushdown(x,l,r);
	int mid=(l+r)>>1;
	if (L<=mid) add(lc,l,mid,L,R,d);
	if (R>mid) add(rc,mid+1,r,L,R,d);
	sum[x]=sum[lc]+sum[rc];
}
ll query(int x,int l,int r,int L,int R){
	if (l>=L&&r<=R) return sum[x];
	pushdown(x,l,r);
	int mid=(l+r)>>1;ll ans=0;
	if (L<=mid) ans+=query(lc,l,mid,L,R);
	if (R>mid) ans+=query(rc,mid+1,r,L,R);
	return ans;
}
struct opt{int tp,T,l,r,d;}Q[N],q[N];
//tp=0表示修改,tp=id表示询问 
bool cmp(const opt &x,const opt &y){
	return x.T==y.T?x.tp<y.tp:x.T<y.T;
}
int n,m,cnt;ll ans[N];
void solve(int l,int r){
	if (l==r) return;
	int mid=(l+r)>>1;
	solve(l,mid);
	solve(mid+1,r);
	int m=0;
	for (int i=l;i<=mid;i++)
		if (!Q[i].tp) q[++m]=Q[i];
	for (int i=mid+1;i<=r;i++)
		if (Q[i].tp) q[++m]=Q[i];
	sort(q+1,q+m+1,cmp);
	for (int i=1;i<=m;i++){
		if (q[i].tp) ans[q[i].tp]+=query(1,1,n,q[i].l,q[i].r);
			else add(1,1,n,q[i].l,q[i].r,q[i].d);
	}
	for (int i=1;i<=m;i++)
		if (!q[i].tp) add(1,1,n,q[i].l,q[i].r,-q[i].d);
}
int main()
{
	freopen("cdcq_a.in","r",stdin);
	freopen("cdcq_a.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++){
		int x;scanf("%d",&x);
		Q[++cnt]=(opt){0,0,i,i,x};
	}
	char s[10]="";
	for (int i=1;i<=m;i++){
		int l,r,d,L,R,D,t;
		scanf("%s%d%d",s,&l,&r);
		if (s[0]=='Q'){
			scanf("%d",&t);
			Q[++cnt]=(opt){i,t,l,r,0};
		}
		else{
			scanf("%d%d%d%d%d",&d,&L,&R,&D,&t);
			Q[++cnt]=(opt){0,t,l,r,-d};
			Q[++cnt]=(opt){0,t,L,R,D};
		}
	}
	solve(1,cnt);
	for (int i=1;i<=cnt;i++)
		if (Q[i].tp) printf("%lld\n",ans[Q[i].tp]);
	return 0;
}