记录编号	335844	评测结果	AAAAAAAAAAT
题目名称	快速红包变换	最终得分	90
用户昵称	白夜<=>黑天	是否通过	未通过
代码语言	C++	运行时间	3.337 s
提交时间	2016-11-02 19:30:35	内存使用	12.88 MiB

#include<cstdio>
#include <cstring>
#define DEFUNC int,int,int,int
#define a_tree int root,int l,int r
 
#define mid ((l+r)>>1)
 
#define this_tree root,l,r
#define left_tree root<<1,l,mid
#define right_tree root<<1|1,mid+1,r
 
#define left_son root<<1
#define right_son root<<1|1
const int MAXN=100010;
const int INF=~0U>>1;
const char *strc[]={"Cadd","Cchange","Cbmax","Cbmin","Qsum","Qwmax","Qwmin","Qnmax","Qnmin"};
const int   OPT []={    1,         0,      3,      2,     2,      1,      0,      1,      0};
const int   CDD []={    0,         0,      0,      0,     0,      0,      0,      1,      1};
struct NODE{
	int num[2];
	NODE(int x=0,int y=0){num[0]=x;num[1]=y;}
};
int w[MAXN];
bool operator <(NODE a,NODE b){return a.num[0]<b.num[0];}
NODE min(NODE a,NODE b){return a.num[0]==b.num[0]?NODE(a.num[0],a.num[1]+b.num[1]):a<b?a:b;}
NODE max(NODE a,NODE b){return a.num[0]==b.num[0]?NODE(a.num[0],a.num[1]+b.num[1]):a<b?b:a;}
NODE sum(NODE a,NODE b){return NODE(a.num[0]+b.num[0],0);}
NODE (*cmper[3])(NODE,NODE)={min,max,sum};
NODE c[MAXN<<2][3];
void rebuild(int);void push_down(int,int,int);
void push_set(DEFUNC);void push_sum(DEFUNC);
void push_max(DEFUNC);void push_min(DEFUNC);
void (*push[4])(DEFUNC)={push_set,push_sum,push_min,push_max};
int lazy[MAXN<<2][2];
int ansl,ansr,number,N_cnt,opt,cdd;
void push_set(a_tree,int val){
	c[root][0]=
	c[root][1]=NODE(val,r-l+1);
	c[root][2].num[0]=val*(r-l+1);
	lazy[root][1]=0;
	lazy[root][0]=val;
}
void push_sum(a_tree,int val){
	c[root][0].num[0]+=val;
	c[root][1].num[0]+=val;
	c[root][2].num[0]+=val*(r-l+1);
	lazy[root][1]+=val;
}
void push_min(a_tree,int val){
	if(c[root][1].num[0]<=val)return;
	if(c[root][0].num[0]>=val){
		push_set(this_tree,val);
		return;
	}if(l==r)return;
	push_down(this_tree);
	push_min(left_tree,val);
	push_min(right_tree,val);
	rebuild(root);
}
void push_max(a_tree,int val){
	if(c[root][0].num[0]>=val)return;
	if(c[root][1].num[0]<=val){
		push_set(this_tree,val);
		return;
	}if(l==r)return;
	push_down(this_tree);
	push_max(left_tree,val);
	push_max(right_tree,val);
	rebuild(root);
}
void rebuild(int root){
	for(int i=0;i<3;++i)
		c[root][i]=cmper[i](c[left_son][i],c[right_son][i]);
}
void push_down(a_tree){
	for(int i=0;i<2;++i)
		if(lazy[root][i]!=0){
			push[i](left_tree,lazy[root][i]);
			push[i](right_tree,lazy[root][i]);
			lazy[root][i]=0;
		}
}
void build(a_tree){
	if(l==r){
		for(int i=0;i<3;++i)
			c[root][i]=NODE(w[l],1);
		return ;
	}build(left_tree);
	build(right_tree);
	rebuild(root);
}
void change(a_tree){
	if(ansl<=l&&r<=ansr){
		push[opt](this_tree,number);
		return;
	}push_down(this_tree);
	if(ansl<=mid)change(left_tree);
	if(ansr> mid)change(right_tree);
	rebuild(root);
}
NODE query(a_tree){
	if(ansl<=l&&r<=ansr)
		return c[root][opt];
	push_down(this_tree);rebuild(root);
	if(ansr<=mid)return query(left_tree);
	if(ansl> mid)return query(right_tree);
	return cmper[opt](query(left_tree),query(right_tree));
}
int QUERY(int l,int r,int seq){
	ansl=l;ansr=r;opt=OPT[seq];cdd=CDD[seq];
	return query(1,1,N_cnt).num[cdd];
}
void CHANGE(int l,int r,int val,int seq){
	ansl=l;ansr=r;number=val;
	opt=OPT[seq];cdd=CDD[seq];
	change(1,1,N_cnt);
}
void BUILD(int N){
	N_cnt=N;build(1,1,N_cnt);
}
int main(){
	freopen("redbag.in","r",stdin);
  	freopen("redbag.out","w",stdout);
	int N,M,x,y,z;
	char sc[7];
	scanf("%d",&N);
	for(int i=1;i<=N;++i)
		scanf("%d",&w[i]);
	BUILD(N);scanf("%d",&M);
	for(int i=1;i<=M;++i){
		scanf("%s",sc);
		for(int j=0;j<9;++j){
			if(strcmp(sc,strc[j])==0){
				if(*sc=='C'){
					scanf("%d%d%d",&x,&y,&z);
					CHANGE(x,y,z,j);
				}else {
					scanf("%d%d",&x,&y);
					printf("%d\n",QUERY(x,y,j));
				}break;
			}
		}
	}
	return 0;
}