注意这题要维护历史最大加和历史最大覆盖
/**************************************************************
Problem: 3064
User: white_hat_hacker
Language: C++
Result: Accepted
Time:3868 ms
Memory:15288 kb
****************************************************************/ #include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define INF 0x7f7f7f7f
#define MAXN 100010
#define rint register int
using namespace std;
int read(){
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if('-'==ch)f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
#define lc k<<1
#define rc k<<1|1
struct SegmentTree{
struct Node{
int L,R;
int vl,_vl;
int add,_add;
int cov,_cov;
bool iscov;
}st[MAXN<<];
int s[MAXN];
void pushup(int k){
st[k].vl=max(st[lc].vl,st[rc].vl);
st[k]._vl=max(st[lc]._vl,st[rc]._vl);
}
void workcov(int k,int cov,int _cov){
st[k].iscov=true;
st[k]._vl=max(st[k]._vl,_cov);
st[k]._cov=max(st[k]._cov,_cov);
st[k].vl=cov;
st[k].cov=cov;
st[k].add=;
}
void workadd(int k,int add,int _add){
if(st[k].iscov){
workcov(k,st[k].cov+add,st[k].cov+_add);
}
else{
st[k]._vl=max(st[k]._vl,st[k].vl+_add);
st[k]._add=max(st[k]._add,st[k].add+_add);
st[k].vl+=add;
st[k].add+=add;
}
}
void pushdown(int k){
int c=k<<;
for(rint i=;i<=;i++){
c|=i;
workadd(c,st[k].add,st[k]._add);
if(st[k].iscov)
workcov(c,st[k].cov,st[k]._cov);
}
st[k].iscov=false;
st[k].add=st[k]._add=;
st[k].cov=st[k]._cov=-INF;
}
void build(int k,int L,int R){
st[k].L=L,st[k].R=R;
st[k].cov=st[k]._cov=-INF;
if(L==R){
st[k].vl=st[k]._vl=s[L];
}
else{
int mid=(L+R)>>;
build(lc,L,mid);
build(rc,mid+,R);
pushup(k);
}
}
void add(int k,int a,int b,int v){
int L=st[k].L,R=st[k].R;
int mid=(L+R)>>;
if(a<=L&&R<=b){
workadd(k,v,v);
}
else{
pushdown(k);
if(a<=mid)add(lc,a,b,v);
if(b>mid)add(rc,a,b,v);
pushup(k);
}
}
void cov(int k,int a,int b,int v){
int L=st[k].L,R=st[k].R;
int mid=(L+R)>>;
if(a<=L&&R<=b){
workcov(k,v,v);
}
else{
pushdown(k);
if(a<=mid)cov(lc,a,b,v);
if(b>mid)cov(rc,a,b,v);
pushup(k);
}
}
int query(int k,int a,int b){
int L=st[k].L,R=st[k].R;
int mid=(L+R)>>;
if(a<=L&&R<=b){
return st[k].vl;
}
else{
pushdown(k);
int ans=-INF;
if(a<=mid)ans=max(ans,query(lc,a,b));
if(b>mid)ans=max(ans,query(rc,a,b));
return ans;
}
}
int _query(int k,int a,int b){
int L=st[k].L,R=st[k].R;
int mid=(L+R)>>;
if(a<=L&&R<=b){
return st[k]._vl;
}
else{
pushdown(k);
int ans=-INF;
if(a<=mid)ans=max(ans,_query(lc,a,b));
if(b>mid)ans=max(ans,_query(rc,a,b));
return ans;
}
}
}ST;
#undef lc
#undef rc
int n;
int main()
{
n=read();
for(rint i=;i<=n;i++){
ST.s[i]=read();
}
ST.build(,,n);
int T=read();
char s[];
int x,y,z;
while(T--){
scanf("%s%d%d",s,&x,&y);
if('Q'==s[])printf("%d\n",ST.query(,x,y));
else if('A'==s[])printf("%d\n",ST._query(,x,y));
else{
scanf("%d",&z);
if('P'==s[])ST.add(,x,y,z);
else ST.cov(,x,y,z);
}
}
return ;
}