记录编号	393757	评测结果	AAAAAAAAAAAAAAAATTAT
题目名称	新史「新幻想史 -现代史-」	最终得分	85
用户昵称	cdcq	是否通过	未通过
代码语言	C++	运行时间	10.416 s
提交时间	2017-04-12 07:47:19	内存使用	16.86 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int rd(){int z=0,mk=1;  char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
	return z*mk;
}
struct dcd{int l,r,value_,time_,id;  bool mark;}a[210000];  int tot=0,query_tot=0;
int n,m,sv[51000];
dcd queue_[210000];
long long value_[810000],delta[810000];
long long ans[210000];
void push_down(int x,int l,int r,int mid){
	value_[x<<1]+=delta[x]*(mid-l+1),value_[x<<1|1]+=delta[x]*(r-mid);
	delta[x<<1]+=delta[x],delta[x<<1|1]+=delta[x];
	delta[x]=0;
}
void get_SegmentTree(int x,int l,int r){
	if(l==r){  value_[x]=sv[l];  return ;}
	int mid=(l+r)>>1;  delta[x]=0;
	get_SegmentTree(x<<1,l,mid),get_SegmentTree(x<<1|1,mid+1,r);
	value_[x]=value_[x<<1]+value_[x<<1|1];
}
void modify(int x,int l,int r,int _left,int _right,long long _value){
	if(l==_left && r==_right){  value_[x]+=_value*(r-l+1),delta[x]+=_value;  return ;}
	int mid=(l+r)>>1;  push_down(x,l,r,mid);
	if(_left<=mid && _right>mid){
		modify(x<<1,l,mid,_left,mid,_value);
		modify(x<<1|1,mid+1,r,mid+1,_right,_value);
	}
	else if(_right<=mid)  modify(x<<1,l,mid,_left,_right,_value);
	else  modify(x<<1|1,mid+1,r,_left,_right,_value);
	value_[x]=value_[x<<1]+value_[x<<1|1];
}
long long query(int x,int l,int r,int _left,int _right){
	if(l==_left && r==_right)  return value_[x];
	int mid=(l+r)>>1;  push_down(x,l,r,mid);
	if(_left<=mid && _right>mid)  return query(x<<1,l,mid,_left,mid)+query(x<<1|1,mid+1,r,mid+1,_right);
	else if(_right<=mid)  return query(x<<1,l,mid,_left,_right);
	else  return query(x<<1|1,mid+1,r,_left,_right);
}
void excdq(int x,int y,int l,int r){//x,y是下标范围，l,r是时间范围
	if(x>y)  return ;
	if(l==r){
		for(int i=x;i<=y;++i){
			if(a[i].mark)  modify(1,1,n,a[i].l,a[i].r,a[i].value_);
			else  ans[a[i].id]+=query(1,1,n,a[i].l,a[i].r);
		}
		for(int i=x;i<=y;++i)
			if(a[i].mark)  modify(1,1,n,a[i].l,a[i].r,-a[i].value_);
		return ;
	}
	int mid=(l+r)>>1;
	int head1=x,head2=x;
	for(int i=x;i<=y;++i){
		if(a[i].mark){//修改
			if(a[i].time_<=mid){
				modify(1,1,n,a[i].l,a[i].r,a[i].value_);
				++head2;
			}
		}
		else{//询问
			if(a[i].time_>mid)  ans[a[i].id]+=query(1,1,n,a[i].l,a[i].r);
			else  ++head2;
		}
	}
	for(int i=x;i<=y;++i)if(a[i].mark && a[i].time_<=mid)
		modify(1,1,n,a[i].l,a[i].r,-a[i].value_);
	for(int i=x;i<=y;++i)  queue_[(a[i].time_ <= mid ? head1 : head2)++]=a[i];
	for(int i=x;i<=y;++i)  a[i]=queue_[i];
	excdq(x,head1-1,l,mid),excdq(head1,y,mid+1,r);
}
int main(){
	freopen("cdcq_a.in","r",stdin);
	freopen("cdcq_a.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;++i)  sv[i]=rd();
	char s[2];
	for(int i=1;i<=m;++i){
		scanf("%s",s);
		if(s[0]=='Q'){
			a[++tot].l=rd(),a[tot].r=rd(),a[tot].time_=rd(),a[tot].mark=false;
			a[tot].id=++query_tot;
		}
		else{
			a[++tot].l=rd(),a[tot].r=rd(),a[tot].value_=-rd(),a[tot].mark=true;
			a[++tot].l=rd(),a[tot].r=rd(),a[tot].value_=rd(),a[tot].mark=true;
			a[tot].time_=a[tot-1].time_=rd();
		}
	}
	excdq(1,tot,0,m);
	get_SegmentTree(1,1,n);
	for(int i=1;i<=tot;++i)if(!a[i].mark)  ans[a[i].id]+=query(1,1,n,a[i].l,a[i].r);
	for(int i=1;i<=query_tot;++i)  printf("%lld\n",ans[i]);
	return 0;
}