记录编号	457671	评测结果	AAAAAAAAAAT
题目名称	快速红包变换	最终得分	90
用户昵称	CSU_Turkey	是否通过	未通过
代码语言	C++	运行时间	1.907 s
提交时间	2017-10-09 08:48:54	内存使用	11.38 MiB

#include<bits/stdc++.h>//噩梦
#define mid ((l+r)>>1)
#define ls o<<1
#define rs o<<1|1
using namespace std;
const int ma=100005;
int n,a[ma],m,Set[ma<<2],add[ma<<2],sum[ma<<2];
struct ghb{
	int fir,sec;
	ghb(){}
	ghb(int x,int y){
		fir=x;sec=y;
	}
	bool operator < (const ghb &o)const{
		return fir<o.fir;
	}
	bool operator == (const ghb &o)const{
		return fir==o.fir;
	}
	ghb operator + (const int &o)const{
		return ghb(fir+o,sec);
	}//+=不能重载！！！ 
	ghb operator + (const ghb &o)const{
		return ghb(fir,sec+o.sec);
	}
}Max[ma<<2],Min[ma<<2];
void update(int l,int r,int o){
	sum[o]=sum[ls]+sum[rs];if(Max[ls]==Max[rs])Max[o]=Max[ls]+Max[rs];else Max[o]=max(Max[ls],Max[rs]);
	if(Min[ls]==Min[rs])Min[o]=Min[ls]+Min[rs];else Min[o]=min(Min[ls],Min[rs]);
}
void build(int l,int r,int o){
	if(l==r){
		sum[o]=a[l];Max[o]=ghb(a[l],1);Min[o]=ghb(a[l],1);return ;
	}build(l,mid,ls);build(mid+1,r,rs);update(l,r,o);return ;
}
void pushdown(int l,int r,int o){
	if(Set[o]!=-1){
		add[ls]=0;add[rs]=0;Set[ls]=Set[o];Set[rs]=Set[o];sum[ls]=(mid-l+1)*Set[o];sum[rs]=(r-mid)*Set[o];
		Max[ls]=ghb(Set[o],mid-l+1);Max[rs]=ghb(Set[o],r-mid);Min[ls]=ghb(Set[o],mid-l+1);Min[rs]=ghb(Set[o],r-mid);Set[o]=-1;
	}
	add[ls]+=add[o];add[rs]+=add[o];
	sum[ls]+=add[o]*(mid-l+1);sum[rs]+=add[o]*(r-mid);
	Max[ls]=Max[ls]+add[o];Min[ls]=Min[ls]+add[o];Max[rs]=Max[rs]+add[o];Min[rs]=Min[rs]+add[o];add[o]=0;
}
void cadd(int l,int r,int o,int L,int R,int x){
	if(l>=L&&r<=R){
		add[o]+=x;sum[o]+=(r-l+1)*x;Max[o]=Max[o]+x;Min[o]=Min[o]+x;return ;
	}pushdown(l,r,o);
	if(mid>=L)cadd(l,mid,ls,L,R,x);if(mid<R)cadd(mid+1,r,rs,L,R,x);
	update(l,r,o);return ;
}
void cchange(int l,int r,int o,int L,int R,int x){
	if(l>=L&&r<=R){
		add[o]=0;Set[o]=x;sum[o]=(r-l+1)*x;Max[o]=ghb(x,r-l+1);Min[o]=ghb(x,r-l+1);return ;
	}pushdown(l,r,o);
	if(mid>=L)cchange(l,mid,ls,L,R,x);if(mid<R)cchange(mid+1,r,rs,L,R,x);
	update(l,r,o);return ;
}
void cbmax(int l,int r,int o,int L,int R,int x){
	if(l>=L&&r<=R){
		if(Max[o].fir<=x){
			Set[o]=x;add[o]=0;sum[o]=(r-l+1)*x;Max[o]=ghb(x,r-l+1);Min[o]=ghb(x,r-l+1);return ;
		}
		else if(Min[o].fir>=x)return ;
	}pushdown(l,r,o);
	if(mid>=L)cbmax(l,mid,ls,L,R,x);if(mid<R)cbmax(mid+1,r,rs,L,R,x);
	update(l,r,o);return ;
}
void cbmin(int l,int r,int o,int L,int R,int x){
	if(l>=L&&r<=R){
		if(Max[o].fir<=x)return ;
		else if(Min[o].fir>=x){
			Set[o]=x;add[o]=0;sum[o]=(r-l+1)*x;Max[o]=ghb(x,r-l+1);Min[o]=ghb(x,r-l+1);return ;
		}
	}pushdown(l,r,o);
	if(mid>=L)cbmin(l,mid,ls,L,R,x);if(mid<R)cbmin(mid+1,r,rs,L,R,x);
	update(l,r,o);return ;
}
int qsum(int l,int r,int o,int L,int R){
	if(l>=L&&r<=R){
		return sum[o];
	}pushdown(l,r,o);int k=0;
	if(mid>=L)k+=qsum(l,mid,ls,L,R);if(mid<R)k+=qsum(mid+1,r,rs,L,R);
	return k;
}
int qwmin(int l,int r,int o,int L,int R){
	if(l>=L&&r<=R){
		return Min[o].fir;
	}pushdown(l,r,o);int k=0x3fffffff;
	if(mid>=L)k=min(k,qwmin(l,mid,ls,L,R));if(mid<R)k=min(k,qwmin(mid+1,r,rs,L,R));
	return k;
}
int qwmax(int l,int r,int o,int L,int R){
	if(l>=L&&r<=R){
		return Max[o].fir;
	}pushdown(l,r,o);int k=-0x3fffffff;
	if(mid>=L)k=max(k,qwmax(l,mid,ls,L,R));if(mid<R)k=max(k,qwmax(mid+1,r,rs,L,R));
	return k;
}
ghb qnmax(int l,int r,int o,int L,int R){
	if(l>=L&&r<=R){
		return Max[o];
	}pushdown(l,r,o);ghb k(-0x3fffffff,0);
	if(mid>=L){
		k=max(k,qnmax(l,mid,ls,L,R));
	}
	if(mid<R){//这里要注意一下啊，，相等的时候需要返回两个相加的 
		ghb u=qnmax(mid+1,r,rs,L,R);
		if(k==u)k=k+u;
		else k=max(k,u);
	}
	return k;
}
ghb qnmin(int l,int r,int o,int L,int R){
	if(l>=L&&r<=R){
		return Min[o];
	}pushdown(l,r,o);ghb k(0x3fffffff,0);
	if(mid>=L){
		k=min(k,qnmin(l,mid,ls,L,R));
	}
	if(mid<R){
		ghb u=qnmin(mid+1,r,rs,L,R);
		if(k==u)k=k+u;
		else k=min(k,u);
	}
	return k;
}
int main()
{
	freopen("redbag.in","r",stdin);freopen("redbag.out","w",stdout);
	scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);
	build(1,n,1);memset(Set,-1,sizeof(Set));
	for(int i=1;i<=m;i++){
		char s[10];int l,r,x;scanf("%s",s);
		if(s[0]=='C'){scanf("%d%d%d",&l,&r,&x);
			if(s[1]=='a')cadd(1,n,1,l,r,x);
			else if(s[1]=='c')cchange(1,n,1,l,r,x);
			else {
				if(s[3]=='a')cbmax(1,n,1,l,r,x);
				else cbmin(1,n,1,l,r,x);
			}
		}
		else {scanf("%d%d",&l,&r);
			if(s[1]=='s')printf("%d\n",qsum(1,n,1,l,r));
			else if(s[1]=='w'){
				if(s[3]=='a')printf("%d\n",qwmax(1,n,1,l,r));
				else printf("%d\n",qwmin(1,n,1,l,r));
			}
			else {
				if(s[3]=='a')printf("%d\n",qnmax(1,n,1,l,r).sec);
				else printf("%d\n",qnmin(1,n,1,l,r).sec);
			}
		}
	}
	return 0;
}