记录编号	414814	评测结果	WWWWWWWWWW
题目名称	[Tyvj 1518] CPU监控	最终得分	0
用户昵称	Anonymity	是否通过	未通过
代码语言	C++	运行时间	0.299 s
提交时间	2017-06-15 09:01:46	内存使用	12.90 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define maxn 400005
#define maxx 100005
using namespace std;
int t,e,pnum[maxx],nmax[maxn],nset[maxn],pmax[maxn],pset[maxn],padd[maxn],nadd[maxn],inf=0x7fffffff;
struct tree{int lc,rc;}tr[maxn];
void pushup(int x)
{
	int lch=x<<1,rch=lch|1;
	nmax[x]=max(nmax[lch],nmax[rch]);
	pmax[x]=max(pmax[lch],pmax[rch]);
}
void build(int x,int y,int z)
{
	tr[z].lc=x;
	tr[z].rc=y;
	nset[z]=-inf;
	pset[z]=-inf;
	if(x==y)
	{
		nmax[z]=pnum[x];
		pmax[z]=pnum[x];
		return;
	}
	int mid=x+y>>1,lch=z<<1,rch=lch|1;
	build(x,mid,lch);
	build(mid+1,y,rch);
	pushup(z);
}
void pushdown(int x)
{
	int lch=x<<1,rch=lch|1;
	pmax[lch]=max(pmax[lch],max(padd[x]+nmax[lch],pset[x]));
	pmax[rch]=max(pmax[rch],max(padd[x]+nmax[rch],pset[x]));
	if(nset[x]==-inf)
	{
		nmax[lch]+=nadd[x];
		nmax[rch]+=nadd[x];
		if(nset[lch]==-inf)
		{	padd[lch]=max(padd[lch],nadd[lch]+padd[x]);
			nadd[lch]+=nadd[x];
		}
		else
		{	pset[lch]=max(pset[lch],nset[lch]+padd[x]);
			//nset[lch]=nmax[lch];//
		}
		if(nset[rch]==-inf)
		{	padd[rch]=max(padd[rch],nadd[rch]+padd[x]);
			nadd[rch]+=nadd[x];
		}
		else
		{	pset[rch]=max(pset[rch],nset[rch]+padd[x]);
			//nset[rch]=nmax[rch];//
		}
	}
	else
	{	
		if(nset[lch]==-inf)
		{	padd[lch]=max(padd[lch],nadd[lch]+padd[x]);
			nadd[lch]+=padd[x];
		}
		else
			pset[lch]=max(pset[lch],nmax[lch]+padd[x]);
		nmax[lch]=nset[lch]=nset[x];
		pset[lch]=max(pset[x],pset[lch]);
		if(nset[rch]==-inf)
		{	padd[rch]=max(padd[rch],nadd[rch]+padd[x]);
			nadd[rch]+=padd[x];
		}
		else
			pset[rch]=max(pset[rch],nmax[rch]+padd[x]);
		nmax[rch]=nset[rch]=nset[x];
		pset[rch]=max(pset[x],pset[rch]);
	}
	nadd[x]=0;
	padd[x]=0;
	nset[x]=-inf;
	pset[x]=-inf;
}
void updata(int x,int y,int z,int v,int o)
{
	if(tr[z].lc>=x&&tr[z].rc<=y)
	{
		if(o)
		{
			nmax[z]=v;
			nset[z]=v;
			pmax[z]=max(pmax[z],nmax[z]);
			pset[z]=max(pset[z],nset[z]);
		}
		else
		{
			nmax[z]+=v;
			pmax[z]=max(pmax[z],nmax[z]);
			if(nset[z]==-inf)
			{	nadd[z]+=v;
				padd[z]=max(padd[z],nadd[z]);
			}
			else
			{	nset[z]=nmax[z];
				pset[z]=max(pset[z],nset[z]);
			}
		}
		return;
	}
	pushdown(z);
	int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1;
	if(x<=mid)
		updata(x,y,lch,v,o);
	if(mid<y)
		updata(x,y,rch,v,o);
	pushup(z);
}
int query(int x,int y,int z,int o)
{
	if(tr[z].lc>=x&&tr[z].rc<=y)
		return o?pmax[z]:nmax[z];
	pushdown(z);
	int mid=tr[z].lc+tr[z].rc>>1,lch=z<<1,rch=lch|1,tmp=-inf;;
	if(x<=mid)
		tmp=max(tmp,query(x,y,lch,o));
	if(mid<y)
		tmp=max(tmp,query(x,y,rch,o));
	return tmp;
}
int main()
{
	freopen("cpuwatcher.in","r",stdin);
	freopen("cpuwatcher.out","w",stdout);
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
		scanf("%d",&pnum[i]);
	int x,y,z;
	build(1,t,1);
	scanf("%d",&e);
	char ord[10];
	for(int i=1;i<=e;i++)
	{
		scanf("%s",ord);
		if(ord[0]=='Q')
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",query(x,y,1,0));
		}
		if(ord[0]=='A')
		{
			scanf("%d%d",&x,&y);
			printf("%d\n",query(x,y,1,1));
		}
		if(ord[0]=='P')
		{
			scanf("%d%d%d",&x,&y,&z);
			updata(x,y,1,z,0);
		}
		if(ord[0]=='C')
		{
			scanf("%d%d%d",&x,&y,&z);
			updata(x,y,1,z,1);
		}
	}
	//while(1);
	return 0;
}