记录编号	408924	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1518] CPU监控	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	0.382 s
提交时间	2017-05-26 10:12:46	内存使用	11.76 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
 
using namespace std;
 
typedef long long LL;
 
void read(int &x) {
    char c; bool flag = 0;
    while((c=getchar())<'0'||c>'9') if(c=='-') flag = 1;
    x=c-'0';while((c=getchar())>='0'&&c<='9') x=x*10+c-'0';
    if(flag) x = -x;
}

void upval(int &a,const int &b) {if(b > a) a = b;}

#define inf 2147483646
#define N 500000
int n,x,y,z,E;

#define L o<<1
#define R o<<1|1
#define lch l,mid,o<<1
#define rch mid+1,r,o<<1|1

struct Node {
	int mv,addv,setv;
	int lmv,ladd,lset;
	void Add (int v) {  // 先push_down 
		mv += v;
		if(mv > lmv) lmv = mv;
		addv += v; 
		upval(ladd,addv);
	}
	void Set(int v) {
		mv = v;
		if(v > lmv) lmv = mv;
		setv = v; 
		upval(lset,setv);
	}
}t[N];

void up(int o) {
	t[o].mv = max(t[L].mv,t[R].mv);
	t[o].lmv = max(t[L].lmv,t[R].lmv);
}

void push_down(int o,int p) {  // stv,addv不同时出现 
	    
	    upval(t[p].lmv,max(t[o].lset,t[p].mv+t[o].ladd));
		if(t[p].setv == -inf) upval(t[p].ladd,t[o].ladd+t[p].addv); ///!!!!
		else upval(t[p].lset,t[p].setv+t[o].ladd);
	    
		if(t[o].addv) {
		    if(t[p].setv == -inf) t[p].addv += t[o].addv;
		    else t[p].setv += t[o].addv;
			t[p].mv += t[o].addv;
		}
		
		if(t[o].setv != -inf) {
			t[p].mv = t[p].setv = t[o].setv;
			t[p].addv = 0;
		}
		
		upval(t[p].lset,max(t[p].setv,t[o].lset));
		upval(t[p].ladd,t[p].addv);
		upval(t[p].lmv,t[p].mv);
}

void push_down(int o) {
	push_down(o,o<<1); push_down(o,o<<1|1);
	t[o].addv = t[o].ladd = 0;
	t[o].setv = t[o].lset = -inf;
}

void build(int l,int r,int o) {
	t[o].lset = t[o].setv = -inf;
	if(l == r) {
		read(t[o].mv); t[o].lmv = t[o].mv;
		return; 
	}
	int mid = (l+r)>>1;
	build(lch); build(rch); 
	up(o);
}

int Max(int l,int r,int o) {
	if(l < r) 	push_down(o);
	if(x <= l && r <= y) return t[o].mv;
	int tmp = -inf,mid = (l+r)>>1;
	if(x <= mid) tmp = Max(lch);
	if(y > mid) tmp = max(tmp,Max(rch)); up(o);
	return tmp;
}

int LMax(int l,int r,int o) {
	if(l < r) 	push_down(o);
	if(x <= l && r <= y) return t[o].lmv;
	int tmp = -inf,mid = (l+r)>>1;
	if(x <= mid) tmp = LMax(lch);
	if(y > mid) tmp = max(tmp,LMax(rch));up(o);
	return tmp;
}

void Add(int l,int r,int o) {
	if(l < r) 	push_down(o);
	if(x <= l && r <= y) {t[o].Add(z);return;}
    int mid = (l+r)>>1;
	if(x <= mid) Add(lch);
	if(y > mid) Add(rch);
	up(o);
}

void Set(int l,int r,int o) {
	if(l < r) 	push_down(o);
	if(x <= l && r <= y) {t[o].Set(z);return;}
    int mid = (l+r)>>1;
	if(x <= mid) Set(lch);
	if(y > mid) Set(rch);
	up(o);
}

int main() {
	freopen("cpuwatcher.in","r",stdin); freopen("cpuwatcher.out","w",stdout);
    read(n); build(1,n,1);
    read(E);
    for (int i = 1; i <= E; i++) {
    	char c;while((c=getchar())<'A'||c>'Z');
    	read(x); read(y); if(c=='P' || c=='C') read(z);
    	if(c == 'Q') printf("%d\n",Max(1,n,1));
    	else if(c == 'A') printf("%d\n",LMax(1,n,1));
    	else if(c == 'P') Add(1,n,1);
    	else Set(1,n,1);
	}
    return 0;
}