题目描述
Bob需要一个程序来监视CPU使用率。这是一个很繁琐的过程，为了让问题更加简单，Bob会慢慢列出今天会在用计算机时做什么事。
Bob会干很多事，除了跑暴力程序看视频之外，还会做出去玩玩和用鼠标乱点之类的事，甚至会一脚踢掉电源……这些事有的会让做这件事的这段时间内CPU使用率增加或减少一个值；有的事还会直接让CPU使用率变为一个值。
当然Bob会询问：在之前给出的事件影响下，CPU在某段时间内，使用率最高是多少。有时候Bob还会好奇地询问，在某段时间内CPU曾经的最高使用率是多少。
为了使计算精确，使用率不用百分比而用一个整数表示。
不保证Bob的事件列表出了莫名的问题，使得使用率为负………………
第一行一个正整数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位整数以内。
题解
这道题如果没有第二个操作的话，就是一道线段树入门题。
现在要求维护历史最大值，我们需要在线段树上的懒标记上下手。
我们令一个标记为(a,b)表示当前add的数为x，达到的最大值为y。
那么合并两个标记(a,b)(c,d)就是(a+c,max(b+c,d))。
最后面的取max是讨论了当前操作是修改还是增量，若增量就取前者，否则取后者。
然后我们对线段树上的每一个节点维护两个标记，当前标记和历史最大标记。
对于历史标记的维护，我们就把当前标记加上刚来的标记后和这个历史标记按位取个max。
对于当前标记直接合并即可。
同时维护两个变量：当前最大值和历史最大值，这个比较好维护。
代码
#include<iostream>
#include<cstdio>
#define ls tr[cnt].l
#define rs tr[cnt].r
#define inf 1e9
#define N 100009
using namespace std;
char s[];
inline int rd(){
int x=;char c=getchar();bool f=;
while(!isdigit(c)){if(c=='-')f=;c=getchar();}
while(isdigit(c)){x=(x<<)+(x<<)+(c^);c=getchar();}
return f?-x:x;
}
struct node{
int x,y;
node(int xx=,int yy=-inf){x=xx;y=yy;}
inline node operator +(const node &b)const{return node(max((int)-inf,x+b.x),max(y+b.x,b.y));}
inline node operator *(const node &b)const{return node(max(x,b.x),max(y,b.y));}
};
int tot=;
struct seg{
int l,r;
node now,la;
int nowmax,lamax;
}tr[N<<];
inline void pushup(int cnt){
tr[cnt].nowmax=max(tr[ls].nowmax,tr[rs].nowmax);
tr[cnt].lamax=max(tr[ls].lamax,tr[rs].lamax);
}
inline void pushdown(int cnt){
node x=tr[cnt].now,y=tr[cnt].la;
tr[rs].la=tr[rs].la*(tr[rs].now+y);
tr[rs].now=tr[rs].now+x;
tr[rs].lamax=max(tr[rs].lamax,max(tr[rs].nowmax+y.x,y.y));
tr[rs].nowmax=max(tr[rs].nowmax+x.x,x.y);
tr[ls].la=tr[ls].la*(tr[ls].now+y);
tr[ls].now=tr[ls].now+x;
tr[ls].lamax=max(tr[ls].lamax,max(tr[ls].nowmax+y.x,y.y));
tr[ls].nowmax=max(tr[ls].nowmax+x.x,x.y);
tr[cnt].now=tr[cnt].la=node();
}
void build(int cnt,int l,int r){
tr[cnt].now=tr[cnt].la=node();
if(l==r){tr[cnt].nowmax=rd();tr[cnt].lamax=tr[cnt].nowmax;return;}
int mid=(l+r)>>;
ls=++tot;rs=++tot;
build(ls,l,mid);build(rs,mid+,r);
pushup(cnt);
}
void upd(int cnt,int l,int r,int L,int R,node x){
if(l>=L&&r<=R){
tr[cnt].la=tr[cnt].la*(tr[cnt].now+x);
tr[cnt].now=tr[cnt].now+x;
tr[cnt].nowmax=max(tr[cnt].nowmax+x.x,x.y);
tr[cnt].lamax=max(tr[cnt].lamax,tr[cnt].nowmax);
return;
}
int mid=(l+r)>>;
pushdown(cnt);
if(mid>=L)upd(ls,l,mid,L,R,x);
if(mid<R)upd(rs,mid+,r,L,R,x);
pushup(cnt);
}
int query(int cnt,int l,int r,int L,int R,int tag){
if(l>=L&&r<=R)return tag?tr[cnt].nowmax:tr[cnt].lamax;
int mid=(l+r)>>;
pushdown(cnt);
if(mid>=L&&mid<R)return max(query(ls,l,mid,L,R,tag),query(rs,mid+,r,L,R,tag));
else if(mid>=L)return query(ls,l,mid,L,R,tag);else if(mid<R)return query(rs,mid+,r,L,R,tag);
}
int main(){
int n=rd();
build(,,n);
int q=rd();int x,y,z;
while(q--){
scanf("%s",s);x=rd();y=rd();
if(s[]=='Q'){
printf("%d\n",query(,,n,x,y,));
}
else if(s[]=='A'){
printf("%d\n",query(,,n,x,y,));
}
else if(s[]=='P'){
z=rd();
upd(,,n,x,y,node(z,-inf));
}
else{
z=rd();
upd(,,n,x,y,node(-inf,z));
}
}
return ;
}