记录编号	335995	评测结果	AAAAAAAAAAT
题目名称	快速红包变换	最终得分	90
用户昵称	_Itachi	是否通过	未通过
代码语言	C++	运行时间	1.680 s
提交时间	2016-11-02 20:54:47	内存使用	7.98 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100005<<2,INF=0x3f3f3f3f;
int n,m,s,t,qx;
int sum[maxn],ma[maxn],mi[maxn],cntma[maxn],cntmi[maxn];
int lzsum[maxn],lzf[maxn];
int Rabit_max(int x,int y){return x>y?x:y;}
int Rabit_min(int x,int y){return x<y?x:y;}
void Rabit_up(int rt){
	int ls=rt<<1,rs=rt<<1|1;
	sum[rt]=sum[ls]+sum[rs];
	if(ma[ls]==ma[rs])ma[rt]=ma[ls],cntma[rt]=cntma[ls]+cntma[rs];
	else{
		if(ma[ls]>ma[rs])ma[rt]=ma[ls],cntma[rt]=cntma[ls];
		else ma[rt]=ma[rs],cntma[rt]=cntma[rs];	
	}
	if(mi[ls]==mi[rs])mi[rt]=mi[ls],cntmi[rt]=cntmi[ls]+cntmi[rs];
	else{
		if(mi[ls]<mi[rs])mi[rt]=mi[ls],cntmi[rt]=cntmi[ls];
		else mi[rt]=mi[rs],cntmi[rt]=cntmi[rs];	
	}
}
void Rabit_down(int rt,int l,int r){
	int mid=(l+r)>>1,ls=rt<<1,rs=rt<<1|1;
	if(lzf[rt]){
		sum[ls]=lzf[rt]*(mid-l+1),lzsum[ls]=0;
		sum[rs]=lzf[rt]*(r-mid),lzsum[rs]=0;
		lzf[ls]=lzf[rs]=ma[ls]=mi[ls]=ma[rs]=mi[rs]=lzf[rt];
		cntma[ls]=cntmi[ls]=mid-l+1;
		cntma[rs]=cntmi[rs]=r-mid;
		lzf[rt]=0;
	}
	if(lzsum[rt]){
		sum[ls]+=lzsum[rt]*(mid-l+1),sum[rs]+=lzsum[rt]*(r-mid);
		if(lzf[ls])lzf[ls]+=lzsum[rt];else lzsum[ls]+=lzsum[rt];
		if(lzf[rs])lzf[rs]+=lzsum[rt];else lzsum[rs]+=lzsum[rt];
		ma[ls]+=lzsum[rt],ma[rs]+=lzsum[rt];
		mi[ls]+=lzsum[rt],mi[rs]+=lzsum[rt];
		lzsum[rt]=0;
	}	
}
#define ls rt<<1,l,mid
#define rs rt<<1|1,mid+1,r
void Rabit_set(int rt,int l,int r){
	if(l==r){
		scanf("%d",&sum[rt]);
		ma[rt]=mi[rt]=sum[rt];
		cntma[rt]=cntmi[rt]=1;
		return;	
	}
	int mid=(l+r)>>1;
	Rabit_set(ls),Rabit_set(rs);
	Rabit_up(rt);
}
void Cadd(int rt,int l,int r){
	if(s<=l&&r<=t){
		sum[rt]+=qx*(r-l+1);
		ma[rt]+=qx,mi[rt]+=qx;
		lzsum[rt]+=qx;
		return;	
	}
	Rabit_down(rt,l,r);
	int mid=(l+r)>>1;
	if(s<=mid)Cadd(ls);
	if(t> mid)Cadd(rs);
	Rabit_up(rt);
}
void Cchange(int rt,int l,int r){
	if(s<=l&&r<=t){
		sum[rt]=qx*(r-l+1);
		ma[rt]=mi[rt]=qx;
		cntma[rt]=cntmi[rt]=r-l+1;
		lzf[rt]=qx;lzsum[rt]=0;
		return;	
	}
	Rabit_down(rt,l,r);
	int mid=(l+r)>>1;
	if(s<=mid)Cchange(ls);
	if(t> mid)Cchange(rs);
	Rabit_up(rt);
}
void Cbmax(int rt,int l,int r){
	if(s<=l&&r<=t&&ma[rt]<=qx){
		sum[rt]=qx*(r-l+1);
		ma[rt]=mi[rt]=qx;
		cntma[rt]=cntmi[rt]=r-l+1;
		lzf[rt]=qx;lzsum[rt]=0;
		return;	
	}
	if(l==r||mi[rt]>=qx)return;
	int mid=(l+r)>>1;
	Rabit_down(rt,l,r);
	if(s<=mid)Cbmax(ls);
	if(t> mid)Cbmax(rs);
	Rabit_up(rt);
}
void Cbmin(int rt,int l,int r){
	if(s<=l&&r<=t&&mi[rt]>=qx){
		sum[rt]=qx*(r-l+1);
		ma[rt]=mi[rt]=qx;
		cntma[rt]=cntmi[rt]=r-l+1;
		lzf[rt]=qx;lzsum[rt]=0;
		return;	
	}
	if(l==r||ma[rt]<=qx)return;
	Rabit_down(rt,l,r);
	int mid=(l+r)>>1;
	if(s<=mid)Cbmin(ls);
	if(t> mid)Cbmin(rs);
	Rabit_up(rt);
}
int Qsum(int rt,int l,int r){
	if(s<=l&&r<=t)return sum[rt];
	Rabit_down(rt,l,r);
	int res=0,mid=(l+r)>>1;
	if(s<=mid)res+=Qsum(ls);
	if(t> mid)res+=Qsum(rs);
	return res;
}
int Qwmax(int rt,int l,int r){
	if(s<=l&&r<=t)return ma[rt];
	Rabit_down(rt,l,r);
	int res=0,mid=(l+r)>>1;
	if(s<=mid)res=Qwmax(ls);
	if(t> mid)res=Rabit_max(res,Qwmax(rs));
	return res;
}
int Qwmin(int rt,int l,int r){
	if(s<=l&&r<=t)return mi[rt];
	Rabit_down(rt,l,r);
	int res=INF,mid=(l+r)>>1;
	if(s<=mid)res=Qwmin(ls);
	if(t> mid)res=Rabit_min(res,Qwmin(rs));
	return res;
}
int w;
int Qnmax(int rt,int l,int r){
	if(s<=l&&r<=t){w=ma[rt];return cntma[rt];}
	Rabit_down(rt,l,r);
	int	mid=(l+r)>>1;
	if(t<=mid)return Qnmax(ls);
	else if(s>mid)return Qnmax(rs);
	else{
		int res,cur,tmp;
		res=Qnmax(ls);cur=w;
		tmp=Qnmax(rs);
		if(cur==w)return res+tmp;
		else if(cur<w)return tmp;
		else{
			w=cur;return res;	
		}
	}
}
int Qnmin(int rt,int l,int r){
	if(s<=l&&r<=t){w=mi[rt];return cntmi[rt];}
	Rabit_down(rt,l,r);
	int	mid=(l+r)>>1;
	if(t<=mid)return Qnmin(ls);
	else if(s>mid)return Qnmin(rs);
	else{
		int res,cur,tmp;
		res=Qnmin(ls);cur=w;
		tmp=Qnmin(rs);
		if(cur==w)return res+tmp;
		else if(cur>w)return tmp;
		else{
			w=cur;return res;	
		}
	}
}
void Rabit_main(){
	scanf("%d",&n);
	Rabit_set(1,1,n);
	scanf("%d",&m);char ope[10];
	while(m--){
		scanf("%s",ope);
		if(ope[0]=='C'){
			scanf("%d%d%d",&s,&t,&qx);
			if(ope[1]=='a')Cadd(1,1,n);
			else if(ope[1]=='c')Cchange(1,1,n);
			else if(ope[3]=='a')Cbmax(1,1,n);
			else Cbmin(1,1,n);
		}
		else{
			scanf("%d%d",&s,&t);
			if(ope[1]=='s')printf("%d\n",Qsum(1,1,n));
			else if(ope[1]=='w'&&ope[3]=='a')printf("%d\n",Qwmax(1,1,n));
			else if(ope[1]=='w')printf("%d\n",Qwmin(1,1,n));
			else if(ope[3]=='a')printf("%d\n",Qnmax(1,1,n));
			else printf("%d\n",Qnmin(1,1,n));
		}	
	}
}
bool _Rabit(),RABIT=_Rabit();int main(){;}
bool _Rabit(){
#define _Rabit _RABIT
#ifdef _Rabit
	freopen("redbag.in","r",stdin);
	freopen("redbag.out","w",stdout);
#endif
	Rabit_main();
#ifndef _Rabit
	getchar(),getchar();
#endif
	fclose(stdin);fclose(stdout);
	return 0;
}