Description
Bob需要一个程序来监视CPU使用率。这是一个很繁琐的过程，为了让问题更加简单，Bob会慢慢列出今天会在用计算机时做什么事。
Bob会干很多事，除了跑暴力程序看视频之外，还会做出去玩玩和用鼠标乱点之类的事，甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内CPU使用率增加或减少一个值；有的事还会直接让CPU使用率变为一个值。
当然Bob会询问：在之前给出的事件影响下，CPU在某段时间内，使用率最高是多少。有时候Bob还会好奇地询问，在某段时间内CPU曾经的最高使用率是多少。
为了使计算精确，使用率不用百分比而用一个整数表示。
不保证Bob的事件列表出了莫名的问题，使得使用率为负………………
Input
第一行一个正整数T，表示Bob需要监视CPU的总时间。
然后第二行给出T个数表示在你的监视程序执行之前，Bob干的事让CPU在这段时间内每个时刻的使用率达已经达到了多少。
第三行给出一个数E，表示Bob需要做的事和询问的总数。
接下来E行每行表示给出一个询问或者列出一条事件：
Q X Y:询问从X到Y这段时间内CPU最高使用率
A X Y:询问从X到Y这段时间内之前列出的事件使CPU达到过的最高使用率
P X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率增加Z
C X Y Z:列出一个事件这个事件使得从X到Y这段时间内CPU使用率变为Z
时间的单位为秒，使用率没有单位。
X和Y均为正整数（X<=Y），Z为一个整数。
从X到Y这段时间包含第X秒和第Y秒。
保证必要运算在有符号32位整数以内。
Output
对于每个询问，输出一行一个整数回答。
Solution
论文题就是强大QAQ
考虑把区间覆盖转化成区间取(max)，标记记成二元组((x,y))，表示先区间加上(x)，再对(y)取(max)，也就是(a_i=max(a_i+x,y))。
那么区间加标记就是((x,-infty))，区间覆盖就是((-infty,x))。
然后对于每个点记两个标记(now)和(history)，表示当前标记和历史最大标记。
那么对于当前标记，将((c,d))向((a,b))上合并，显然结果是((a+c,max(b+c,d)))。
对于历史最大标记，标记((a,b))可以看成是一个形如(y=max(x+a,b))的函数，显然这是个分段函数，第一段是(y=b)，第二段是(y=x+a)，两个标记合并对于每个(x)都是要取最大值，所以取函数最上面那一段，标记((a,b))和((c,d))合并的结果就是((max(a,c),max(b,d)))。
然后具体看代码吧，(我能说我因为fread挂了而T了一版吗QAQ)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
namespace fast_IO {
template <typename T> inline void read(T &x) {
x=0;T f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
template <typename T,typename... Args> inline void read(T& x,Args& ...args) {
read(x),read(args...);
}
char buf2[1<<21],a[80];int p,p3=-1;
inline void flush() {fwrite(buf2,1,p3+1,stdout),p3=-1;}
template <typename T> inline void write(T x) {
if(p3>(1<<20)) flush();
if(x<0) buf2[++p3]='-',x=-x;
do {a[++p]=x%10+48;} while(x/=10);
do {buf2[++p3]=a[p];} while(--p);
buf2[++p3]='
';
}
template <typename T,typename... Args> inline void write(T x,Args ...args) {
write(x),write(args...);
}
}
using fast_IO :: read;
using fast_IO :: write;
using fast_IO :: flush;
const int maxn = 1e5+10;
const int inf = 0x3f3f3f3f;
int n,m,val[maxn];
char s[10];
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
struct Segment_Tree {
int hmax[maxn<<2],nmax[maxn<<2];
struct tag {
int add,mx;
inline void init() {add=0,mx=-inf;}
inline tag operator + (const tag &rhs) const {return (tag){max(-inf,add+rhs.add),max(mx+rhs.add,rhs.mx)};}
inline tag operator * (const tag &rhs) const {return (tag){max(add,rhs.add),max(mx,rhs.mx)};}
}nlazy[maxn<<2],hlazy[maxn<<2];
inline void update(int p) {
hmax[p]=max(hmax[ls],hmax[rs]);
nmax[p]=max(nmax[ls],nmax[rs]);
}
inline void push_tag(int p,tag now,tag history) {
hlazy[p]=hlazy[p]*(nlazy[p]+history);
nlazy[p]=nlazy[p]+now;
hmax[p]=max(hmax[p],max(nmax[p]+history.add,history.mx));
nmax[p]=max(nmax[p]+now.add,now.mx);
}
inline void pushdown(int p) {
push_tag(ls,nlazy[p],hlazy[p]);
push_tag(rs,nlazy[p],hlazy[p]);
nlazy[p].init(),hlazy[p].init();
}
void modify(int p,int l,int r,int x,int y,int add,int mx) {
if(x<=l&&r<=y) return push_tag(p,(tag){add,mx},(tag){add,mx}),void();
pushdown(p);
if(x<=mid) modify(ls,l,mid,x,y,add,mx);
if(y>mid) modify(rs,mid+1,r,x,y,add,mx);
update(p);
}
int query_hmax(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return hmax[p];
int ans=-inf;pushdown(p);
if(x<=mid) ans=max(ans,query_hmax(ls,l,mid,x,y));
if(y>mid) ans=max(ans,query_hmax(rs,mid+1,r,x,y));
return ans;
}
int query_nmax(int p,int l,int r,int x,int y) {
if(x<=l&&r<=y) return nmax[p];
int ans=-inf;pushdown(p);
if(x<=mid) ans=max(ans,query_nmax(ls,l,mid,x,y));
if(y>mid) ans=max(ans,query_nmax(rs,mid+1,r,x,y));
return ans;
}
void build(int p,int l,int r) {
hlazy[p].init(),nlazy[p].init();
if(l==r) return hmax[p]=nmax[p]=val[l],void();
build(ls,l,mid),build(rs,mid+1,r),update(p);
}
}SGT;
#undef ls
#undef rs
#undef mid
int main() {
read(n);
for(int i=1;i<=n;i++) read(val[i]);
SGT.build(1,1,n);
read(m);
for(int i=1;i<=m;i++) {
scanf("%s",s+1);int x,y,z;read(x,y);
if(s[1]=='Q') write(SGT.query_nmax(1,1,n,x,y));
else if(s[1]=='A') write(SGT.query_hmax(1,1,n,x,y));
else if(s[1]=='P') read(z),SGT.modify(1,1,n,x,y,z,-inf);
else read(z),SGT.modify(1,1,n,x,y,-inf,z);
}
flush();
return 0;
}