记录编号	414944	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1518] CPU监控	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.316 s
提交时间	2017-06-15 11:54:10	内存使用	9.85 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1<<31;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum*f;
}
int n,m;
int v[100001];
int padd[400001],pset[400001],pmx[400001];
int nadd[400001],nset[400001],nmx[400001];
inline int my_max(int a,int b){
	return a>b?a:b;
}
inline void pushup(int i){
	int l(i<<1),r(l|1);
	pmx[i]=my_max(pmx[l],pmx[r]);
	nmx[i]=my_max(nmx[l],nmx[r]);
}
inline void pushdown(int rt){
	int ch(rt<<1);
	for(int i=0;i<=1;i++){
		int nowch(ch+i);
		pmx[nowch]=my_max(pmx[nowch],my_max(padd[rt]+nmx[nowch],pset[rt]));
		if(nset[rt]==inf){
			nmx[nowch]+=nadd[rt];
			if(nset[nowch]==inf){
				padd[nowch]=my_max(padd[nowch],nadd[nowch]+padd[rt]);
				nadd[nowch]+=nadd[rt];
			}
			else{
				pset[nowch]=my_max(pset[nowch],nset[nowch]+padd[rt]);
				nset[nowch]=nmx[nowch];
			}
		}
		else{
			if(nset[nowch]==inf){
				padd[nowch]=my_max(padd[nowch],nadd[nowch]+padd[rt]);
				nadd[nowch]+=padd[rt];
			}
			else
				pset[nowch]=my_max(pset[nowch],nmx[nowch]+padd[rt]);
			nmx[nowch]=nset[rt];
			nset[nowch]=nset[rt];
			pset[nowch]=my_max(pset[rt],pset[nowch]);
		}
	}
	nadd[rt]=0;
	padd[rt]=0;
	nset[rt]=inf;
	pset[rt]=inf;
}
inline void build(int l,int r,int i){
	padd[i]=0;
	pset[i]=inf;
	nadd[i]=0;
	nset[i]=inf;
	if(l==r){
		pmx[i]=v[l];
		nmx[i]=v[l];
		return;
	}
	int lc(i<<1),rc(lc|1),mid((l+r)>>1);
	build(l,mid,lc);
	build(mid+1,r,rc);
	pushup(i);
}
inline void update_set(int ll,int rr,int c,int l,int r,int i){
	if(ll<=l&&r<=rr){
		nset[i]=c;
		nmx[i]=c;
		pset[i]=my_max(pset[i],nset[i]);
		pmx[i]=my_max(pmx[i],nmx[i]);
		return;
	}
	pushdown(i);
	int lc(i<<1),rc(lc|1),mid((l+r)>>1);
	if(ll<=mid)
		update_set(ll,rr,c,l,mid,lc);
	if(rr>mid)
		update_set(ll,rr,c,mid+1,r,rc);
	pushup(i);
}
inline void update_add(int ll,int rr,int c,int l,int r,int i){
	if(ll<=l&&r<=rr){
		nmx[i]+=c;
		pmx[i]=my_max(pmx[i],nmx[i]);
		if(nset[i]==inf){
			nadd[i]+=c;
			padd[i]=my_max(padd[i],nadd[i]);
		}
		else{
			nset[i]=nmx[i];
			pset[i]=my_max(pset[i],nset[i]);
		}
		return;
	}
	pushdown(i);
	int lc(i<<1),rc(lc|1),mid((l+r)>>1);
	if(ll<=mid)
		update_add(ll,rr,c,l,mid,lc);
	if(rr>mid)
		update_add(ll,rr,c,mid+1,r,rc);
	pushup(i);
}
inline int query_p(int ll,int rr,int l,int r,int i){
	if(ll<=l&&r<=rr)
		return pmx[i];
	pushdown(i);
	int lc(i<<1),rc(lc|1),mid((l+r)>>1);
	int ret(inf);
	if(ll<=mid)
		ret=my_max(ret,query_p(ll,rr,l,mid,lc));
	if(rr>mid)
		ret=my_max(ret,query_p(ll,rr,mid+1,r,rc));
	return ret;
}
inline int query_n(int ll,int rr,int l,int r,int i){
	if(ll<=l&&r<=rr)
		return nmx[i];
	pushdown(i);
	int lc(i<<1),rc(lc|1),mid((l+r)>>1);
	int ret(inf);
	if(ll<=mid)
		ret=my_max(ret,query_n(ll,rr,l,mid,lc));
	if(rr>mid)
		ret=my_max(ret,query_n(ll,rr,mid+1,r,rc));
	return ret;
}
inline void write(int x){
	if(x==0){
		putchar('0');
		return;
	}if(x<0)
		putchar('-'),x=-x;
	int len=0,buf[15];
	while(x)
		buf[len++]=x%10,x/=10;
	for(int i=len-1;i>=0;i--)
		putchar(buf[i]+'0');
	return;
}
int main(){
	freopen("cpuwatcher.in","r",stdin);
	freopen("cpuwatcher.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
		v[i]=read();
	/*for(int i=1;i<=n;i++)
		cout<<v[i]<<' ';*/
	build(1,n,1);
	m=read();
	char op[2];
	while(m--){
		scanf("%s",op);
		if(op[0]=='Q'){
			int x(read()),y(read());
			write(query_n(x,y,1,n,1));
			continue;
		}
		if(op[0]=='A'){
			int x(read()),y(read());
			write(query_p(x,y,1,n,1));
			continue;
		}
		if(op[0]=='P'){
			int x(read()),y(read()),z(read());
			update_add(x,y,z,1,n,1);
			continue;
		}
		if(op[0]=='C'){
			int x(read()),y(read()),z(read());
			update_set(x,y,z,1,n,1);
			continue;
		}
	}//while(1);
}