CPU监控
这种题就需要小黄鸭调试法，不行就重构，动态gdb可能会死人，一堆tag的...
维护历史最值的一个核心是历史最值tag，它的意义是从上一次这个点下放tag之后到当前时刻的这个点的tag达到过的最大值。
我们注意到tag的作用是按找时间限制的，所以我们可以认为历史最大tag是一个前缀最大值。
有了历史最值tag，我们就可以完成pushdown的工作辣
就把历史tag放给儿子的历史tag和历史最值，这时候更新需要用儿子的当前值结合自己的历史最大进行更新。
对这个题维护一个二元组\(tag(a,b)\)，这个tag对值\(v\)就表示\(\max(v+a,b)\)，区间加就是\((c,-inf)\)，区间覆盖\((-inf,c)\)
考虑两个按时间顺序的tag的合并(a,b)与(c,d)，那么合并以后是\((a+c,\max(b+c,d))\)
注意\(a+c\)对\(-inf\)取个\(\max\)，否则可能会爆掉int...
然后注意一下细节就可以了
Code:
#include <cstdio>
#include <cctype>
#include <algorithm>
using std::max;
template <class T>
void read(T &x)
{
int f=0;x=0;char c=getchar();
while(!isdigit(c)) f|=c=='-',c=getchar();
while(isdigit(c)) x=x*10+c-'0',c=getchar();
if(f) x=-x;
}
const int inf=0x3f3f3f3f;
const int N=1e5+10;
#define ls id<<1
#define rs id<<1|1
int n,m,a[N];
struct koito_yuu
{
int a,b;
koito_yuu(){}
koito_yuu(int A,int B){a=A,b=B;}
koito_yuu friend operator +(koito_yuu a,koito_yuu b){return koito_yuu(max(-inf,a.a+b.a),max(a.b+b.a,b.b));}
int friend operator +(koito_yuu a,int b){return max(a.a+b,a.b);}
void upt(koito_yuu v){a=max(a,v.a),b=max(b,v.b);}
}tag[N<<2],histag[N<<2];
int mx[N<<2],hismx[N<<2];
void updata(int id)
{
mx[id]=max(mx[ls],mx[rs]);
hismx[id]=max(hismx[ls],hismx[rs]);
}
void pushdown(int id)
{
if(tag[id].a||tag[id].b!=-inf)
{
hismx[ls]=max(hismx[ls],histag[id]+mx[ls]);
hismx[rs]=max(hismx[rs],histag[id]+mx[rs]);
histag[ls].upt(tag[ls]+histag[id]);
histag[rs].upt(tag[rs]+histag[id]);
histag[id]=koito_yuu(0,-inf);
tag[ls]=tag[ls]+tag[id];
tag[rs]=tag[rs]+tag[id];
mx[ls]=tag[id]+mx[ls];
mx[rs]=tag[id]+mx[rs];
tag[id]=koito_yuu(0,-inf);
}
}
void build(int id,int l,int r)
{
tag[id]=histag[id]=koito_yuu(0,-inf);
if(l==r)
{
mx[id]=hismx[id]=a[l];
return;
}
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
updata(id);
}
int query(int id,int L,int R,int l,int r)
{
if(l==L&&r==R) return mx[id];
pushdown(id);
int Mid=L+R>>1;
if(r<=Mid) return query(ls,L,Mid,l,r);
else if(l>Mid) return query(rs,Mid+1,R,l,r);
else return max(query(ls,L,Mid,l,Mid),query(rs,Mid+1,R,Mid+1,r));
}
int hisquery(int id,int L,int R,int l,int r)
{
if(l==L&&r==R) return hismx[id];
pushdown(id);
int Mid=L+R>>1;
if(r<=Mid) return hisquery(ls,L,Mid,l,r);
else if(l>Mid) return hisquery(rs,Mid+1,R,l,r);
else return max(hisquery(ls,L,Mid,l,Mid),hisquery(rs,Mid+1,R,Mid+1,r));
}
void change(int id,int L,int R,int l,int r,koito_yuu d)
{
if(l==L&&r==R)
{
hismx[id]=max(hismx[id],d+mx[id]);
histag[id].upt(tag[id]+d);
mx[id]=d+mx[id];
tag[id]=tag[id]+d;
return;
}
pushdown(id);
int Mid=L+R>>1;
if(r<=Mid) change(ls,L,Mid,l,r,d);
else if(l>Mid) change(rs,Mid+1,R,l,r,d);
else change(ls,L,Mid,l,Mid,d),change(rs,Mid+1,R,Mid+1,r,d);
updata(id);
}
int main()
{
read(n);
for(int i=1;i<=n;i++) read(a[i]);
build(1,1,n);
read(m);
char op[4];
for(int l,r,x,i=1;i<=m;i++)
{
scanf("%s",op);
read(l),read(r);
if(op[0]=='Q') printf("%d\n",query(1,1,n,l,r));
else if(op[0]=='A') printf("%d\n",hisquery(1,1,n,l,r));
else if(op[0]=='P')
{
read(x);
change(1,1,n,l,r,koito_yuu(x,-inf));
}
else
{
read(x);
change(1,1,n,l,r,koito_yuu(-inf,x));
}
}
return 0;
}
2019.3.21