记录编号	395144	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	新史「新幻想史 -现代史-」	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.346 s
提交时间	2017-04-15 09:54:02	内存使用	2.69 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50010;
struct A{int t,u,v,w,l,r,d;}a[maxn],b[maxn];
void CDQ(int,int);
void modify(int,int,int);
long long query(int,int);
void add(int,long long,long long*);
long long query(int,long long*);
long long seq[maxn],c[2][maxn],ans[maxn];
char op;
int n,m;
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++){
		scanf("%lld",&seq[i]);
		seq[i]+=seq[i-1];
	}
	for(int i=1;i<=m;i++){
		scanf(" %c%d%d",&op,&a[i].l,&a[i].r);
		if(op=='Q'){
			scanf("%d",&a[i].t);
			ans[i]=seq[a[i].r]-seq[a[i].l-1];
			a[i].d=i;
		}
		else{
			a[i].u=a[i].l;
			a[i].v=a[i].r;
			scanf("%d%d%d%d%d",&a[i].w,&a[i].l,&a[i].r,&a[i].d,&a[i].t);
			ans[i]=1ull<<63;
		}
	}
	CDQ(1,m);
	for(int i=1;i<=m;i++)if(ans[i]!=(1ull<<63))printf("%lld\n",ans[i]);
	return 0;
}
void CDQ(int l,int r){
	if(l==r)return;
	int mid=(l+r)>>1;
	CDQ(l,mid);
	CDQ(mid+1,r);
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(a[i].t<a[j].t||(a[i].t==a[j].t&&a[i].v)){
			if(a[i].v){//printf("WTF?!!");
				modify(a[i].u,a[i].v,-a[i].w);
				modify(a[i].l,a[i].r,a[i].d);
			}
			b[k++]=a[i++];
		}
		else{
			if(!a[j].v)ans[a[j].d]+=query(a[j].l,a[j].r);
			b[k++]=a[j++];
		}
	}
	while(i<=mid){
		if(a[i].v){
			modify(a[i].u,a[i].v,-a[i].w);
			modify(a[i].l,a[i].r,a[i].d);
		}
		b[k++]=a[i++];
	}
	while(j<=r){
		if(!a[j].v)ans[a[j].d]+=query(a[j].l,a[j].r);
		b[k++]=a[j++];
	}
	for(i=l;i<=mid;i++)if(a[i].v){
		modify(a[i].u,a[i].v,a[i].w);
		modify(a[i].l,a[i].r,-a[i].d);
	}
	copy(b+l,b+r+1,a+l);
}
void modify(int l,int r,int d){
	add(l,(long long)(1-l)*d,c[0]);
	add(r+1,(long long)r*d,c[0]);
	add(l,d,c[1]);
	add(r+1,-d,c[1]);
}
long long query(int l,int r){
	return (query(r,c[0])+query(r,c[1])*r)-(query(l-1,c[0])+query(l-1,c[1])*(l-1));
}
void add(int x,long long d,long long *c){
	while(x<=n){
		c[x]+=d;
		x+=x&-x;
	}
}
long long query(int x,long long *c){
	long long ans=0;
	while(x){
		ans+=c[x];
		x&=x-1;
	}
	return ans;
}