记录编号	144719	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1518] CPU监控	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.887 s
提交时间	2014-12-26 16:36:18	内存使用	13.65 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL INF=1e12;
const int SIZEN=100010;
inline void Set_Max(LL &a,LL b){a=max(a,b);}
class Node{
public:
	int lc,rc;
	int left,right;
	bool have_set;
	LL cur_mx,cur_add,cur_set;
	LL ever_mx,ever_add,ever_set;
	#define lc(x) Tree[x].lc
	#define rc(x) Tree[x].rc
	#define left(x) Tree[x].left
	#define right(x) Tree[x].right
	#define have_set(x) Tree[x].have_set
	#define cur_mx(x) Tree[x].cur_mx
	#define cur_add(x) Tree[x].cur_add
	#define cur_set(x) Tree[x].cur_set
	#define ever_mx(x) Tree[x].ever_mx
	#define ever_add(x) Tree[x].ever_add
	#define ever_set(x) Tree[x].ever_set
};
Node Tree[2*SIZEN];
int tot=0;
void Clear_Lazy(int x){
	have_set(x)=false;
	cur_add(x)=0,cur_set(x)=-INF;
	ever_add(x)=0,ever_set(x)=-INF;
}
void Add_Lazy(int x,int fa){
	if(!x||!fa) return;
	//ever_mx
	Set_Max(ever_mx(x),cur_mx(x)+ever_add(fa));
	if(have_set(fa)) Set_Max(ever_mx(x),ever_set(fa));
	//ever_add
	if(!have_set(x)) Set_Max(ever_add(x),cur_add(x)+ever_add(fa));
	//ever_set
	if(have_set(x)) Set_Max(ever_set(x),cur_set(x)+ever_add(fa));
	if(have_set(fa)) Set_Max(ever_set(x),ever_set(fa));
	//curs
	if(have_set(fa)){
		cur_mx(x)=cur_set(fa);
		cur_add(x)=0;
		cur_set(x)=cur_set(fa);
		have_set(x)=true;
	}
	else{
		if(have_set(x)){
			cur_mx(x)+=cur_add(fa);
			cur_add(x)=0;
			cur_set(x)+=cur_add(fa);
			have_set(x)=true;
		}
		else{
			cur_mx(x)+=cur_add(fa);
			cur_add(x)+=cur_add(fa);
			cur_set(x)=0;
			have_set(x)=false;
		}
	}
}
void Push_Down(int x){
	if(!x) return;
	Add_Lazy(lc(x),x);
	Add_Lazy(rc(x),x);
	Clear_Lazy(x);
}
void Update(int x){
	if(!x||!lc(x)) return;
	cur_mx(x)=max(cur_mx(lc(x)),cur_mx(rc(x)));
	ever_mx(x)=max(ever_mx(lc(x)),ever_mx(rc(x)));
}
int Build(int a[],int l,int r){
	int p=++tot;
	left(p)=l,right(p)=r;
	Clear_Lazy(p);
	if(l==r){
		cur_mx(p)=ever_mx(p)=a[l];
		lc(p)=rc(p)=0;
	}
	else{
		int mid=(l+r)/2;
		lc(p)=Build(a,l,mid);
		rc(p)=Build(a,mid+1,r);
		Update(p);
	}
	return p;
}
LL Query_Cur(int p,int l,int r){
	Push_Down(p);
	if(!p||l>right(p)||r<left(p)) return -INF;
	if(left(p)>=l&&right(p)<=r) return cur_mx(p);
	return max(Query_Cur(lc(p),l,r),Query_Cur(rc(p),l,r));
}
LL Query_Ever(int p,int l,int r){
	Push_Down(p);
	if(!p||l>right(p)||r<left(p)) return -INF;
	if(left(p)>=l&&right(p)<=r) return ever_mx(p);
	return max(Query_Ever(lc(p),l,r),Query_Ever(rc(p),l,r));
}
void Change(int p,int l,int r,int upd){
	Push_Down(p);
	if(!p||l>right(p)||r<left(p)) return;
	if(left(p)>=l&&right(p)<=r) Add_Lazy(p,upd);
	else{
		Change(lc(p),l,r,upd);
		Change(rc(p),l,r,upd);
		Update(p);
	}
}
void Seg_Add(int l,int r,int t){
	int k=tot+1;
	have_set(k)=false;
	cur_add(k)=t;ever_add(k)=max(0,t);
	cur_set(k)=-INF;ever_set(k)=-INF;
	Change(1,l,r,k);
}
void Seg_Set(int l,int r,int t){
	int k=tot+1;
	have_set(k)=true;
	cur_add(k)=0;ever_add(k)=0;
	cur_set(k)=t;ever_set(k)=t;
	Change(1,l,r,k);
}
int N,Q;
int A[SIZEN];
void Work(void){
	Build(A,1,N);
	scanf("%d",&Q);
	char cmd[3];
	int x,y,z;
	for(int i=1;i<=Q;i++){
		scanf("%s",cmd);
		if(cmd[0]=='Q'){
			scanf("%d%d",&x,&y);
			printf("%lld\n",Query_Cur(1,x,y));
		}
		else if(cmd[0]=='A'){
			scanf("%d%d",&x,&y);
			printf("%lld\n",Query_Ever(1,x,y));
		}
		else if(cmd[0]=='P'){
			scanf("%d%d%d",&x,&y,&z);
			Seg_Add(x,y,z);
		}
		else if(cmd[0]=='C'){
			scanf("%d%d%d",&x,&y,&z);
			Seg_Set(x,y,z);
		}
	}
}
void Read(void){
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
}
int main(){
	freopen("cpuwatcher.in","r",stdin);
	freopen("cpuwatcher.out","w",stdout);
	Read();
	Work();
	return 0;
}