题目：[BZOJ3064][Tyvj1518] CPU监控
思路：
线段树专题讲的。以下为讲课时的课件：
方法一：
果然写自闭了...
最后差不多是对着题解看上几遍然后抄的。
最初容易把问题想简单，以为只要随便用个gmax表示历史最大值，然后就能直接维护了。
实际上，考虑这种情况：我们对一段区间曾做过一些操作，标记停留在某层还没有被下放。之后又进行一项新的操作，把原有的标记覆盖掉了，于是在维护子节点的gmax值时就会出错。
那么该怎么做呢？
为了防止信息丢失，必须保证每次pushdown之前，还没有被下放的标记能够更新子节点的gmax，然后才能把这个标记覆盖掉。
如果每次pushdown都先把原来标记下放一遍，复杂度会退化->TLE.
我们可以维护“从上次pushdown到现在为止没有被下放的最大add值和set值”，问题就解决了。
以上是基本思想，只涉及线段树最基本的lazytag，但具体实现需要对lazy标记的下放有深刻的理解。
题目中有两个操作：add和set，我们考虑下放顺序，共四种情况：
- add - add
- set - set
- set - add
- add - set
前两种直接维护，第三种可以把add累加到set上。
于是能做了，有的题解就是直接分两类讨论：add-add，add-set。
这里我们也可以按讲课时的方法，用set盖掉add，于是任意时刻线段树节点上只会出现一种标记。可以在提交的代码中加入断言进行验证。
注意区分：
mx、add、set标记只会在Add操作、Set操作、pushdown时父节点的add和set标记时更新，gmax、gadd、gset在各种操作时都可能被更新。
把不同的更新分别写成函数，可以帮助整理思维。
Code：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6,inf=0x3f3f3f3f;
int n,T,ans_max,ans_gmax;
struct Tree{
int l,r,mx,gmx,add,gadd,set,gset;
#define l(p) (node[p].l)
#define r(p) (node[p].r)
#define mx(p) (node[p].mx)
#define gmx(p) (node[p].gmx)
#define add(p) (node[p].add)
#define gadd(p) (node[p].gadd)
#define set(p) (node[p].set)
#define gset(p) (node[p].gset)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l(p)+r(p))>>1)
}node[N<<2];
inline void cmax(int &a,int b){ a=((b>a)?b:a); }
void pup(int p){
mx(p)=max(mx(ls(p)),mx(rs(p)));
cmax(gmx(p),max(gmx(ls(p)),gmx(rs(p))));
}
void build(int p,int l,int r){
l(p)=l;r(p)=r;
set(p)=gset(p)=-inf;
if(l==r){
scanf("%lld",&mx(p));
gmx(p)=mx(p);
return;
}
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pup(p);
}
void m_add(int p,int val){/*p节点实际增加val*/
cmax(gmx(p),mx(p)+=val);
if(set(p)!=-inf) cmax(gset(p),set(p)+=val);
else cmax(gadd(p),add(p)+=val);
}
void m_set(int p,int val){/*p节点实际被val覆盖*/
cmax(gmx(p),mx(p)=val);
cmax(gset(p),set(p)=val);
add(p)=0;
}
void g_add(int p,int val){/*用父亲的gadd更新p节点*/
cmax(gmx(p),mx(p)+val);
if(set(p)!=-inf) cmax(gset(p),set(p)+val);
else cmax(gadd(p),add(p)+val);
}
void g_set(int p,int val){/*用父亲的gset更新p节点*/
cmax(gmx(p),val);
cmax(gset(p),val);
}
void pdown(int p){
if(gadd(p)){
g_add(ls(p),gadd(p));
g_add(rs(p),gadd(p));
gadd(p)=0;
}
if(gset(p)!=-inf){
g_set(ls(p),gset(p));
g_set(rs(p),gset(p));
gset(p)=-inf;
}
if(add(p)){
m_add(ls(p),add(p));
m_add(rs(p),add(p));
add(p)=0;
}
if(set(p)!=-inf){
m_set(ls(p),set(p));
m_set(rs(p),set(p));
set(p)=-inf;
}
}
void Add(int p,int L,int R,int val){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) return m_add(p,val);
pdown(p);
Add(ls(p),L,R,val);
Add(rs(p),L,R,val);
pup(p);
}
void Set(int p,int L,int R,int val){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) return m_set(p,val);
pdown(p);
Set(ls(p),L,R,val);
Set(rs(p),L,R,val);
pup(p);
}
void query(int p,int L,int R){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) {
ans_max=max(ans_max,mx(p));
ans_gmax=max(ans_gmax,gmx(p));
return;
}
pdown(p);
query(ls(p),L,R);
query(rs(p),L,R);
}
int main(){
scanf("%d",&n);
build(1,1,n);
scanf("%d",&T);
char op[5];
int x,y,z;
while(T--){
ans_max=ans_gmax=-inf;
scanf("%s",op);
if(op[0]=='Q') {
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",ans_max);
} else if(op[0]=='A') {
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",ans_gmax);
} else if(op[0]=='P') {
scanf("%d%d%d",&x,&y,&z);
Add(1,x,y,z);
} else if(op[0]=='C') {
scanf("%d%d%d",&x,&y,&z);
Set(1,x,y,z);
}
}
return 0;
}
方法二：
康题解的时候发现还有一种巧妙的标记。
以下转载某dalao的博客。
这种标记很妙啊，好像又是出自集训队论文，抽空再研究。
先对着题解抄一份。
注意细节：两个标记合并时，add与-inf取max，防止赋值操作add值连加几个-inf爆了int。
Code
#include <bits/stdc++.h>
using namespace std;
const int N=1e6,inf=0x3f3f3f3f;
int n,T,ans_max,ans_gmax;
struct tag{
int add,set;
inline tag(int add=0,int set=-inf):add(add),set(set){}
inline tag operator + (const tag &b){
return tag(max(-inf,add+b.add),max(set+b.add,b.set));
}
inline tag operator & (const tag &b){
return tag(max(add,b.add),max(set,b.set));
}
};
struct Tree{
int l,r,mx,gmx;tag now,pre;
#define l(p) (node[p].l)
#define r(p) (node[p].r)
#define mx(p) (node[p].mx)
#define gmx(p) (node[p].gmx)
#define now(p) (node[p].now)
#define pre(p) (node[p].pre)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mid ((l(p)+r(p))>>1)
}node[N<<2];
inline void cmax(int &a,int b){ a=((b>a)?b:a); }
void pup(int p){
mx(p)=max(mx(ls(p)),mx(rs(p)));
cmax(gmx(p),max(gmx(ls(p)),gmx(rs(p))));
}
void build(int p,int l,int r){
l(p)=l;r(p)=r;
now(p)=pre(p)=tag();
if(l==r){
scanf("%lld",&mx(p));
gmx(p)=mx(p);
return;
}
build(ls(p),l,mid);
build(rs(p),mid+1,r);
pup(p);
}
void calc(int p,tag n,tag h){
pre(p)=pre(p)&(now(p)+h);
now(p)=now(p)+n;
cmax(gmx(p),max(mx(p)+h.add,h.set));
mx(p)=max(mx(p)+n.add,n.set);
}
void pdown(int p){
calc(ls(p),now(p),pre(p));
calc(rs(p),now(p),pre(p));
now(p)=pre(p)=tag();
}
void change(int p,int L,int R,tag key){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) return calc(p,key,key);
pdown(p);
change(ls(p),L,R,key);
change(rs(p),L,R,key);
pup(p);
}
void query(int p,int L,int R){
if(l(p)>R||r(p)<L) return;
if(L<=l(p)&&r(p)<=R) {
ans_max=max(ans_max,mx(p));
ans_gmax=max(ans_gmax,gmx(p));
return;
}
pdown(p);
query(ls(p),L,R);
query(rs(p),L,R);
}
int main(){
scanf("%d",&n);
build(1,1,n);
scanf("%d",&T);
char op[5];
int x,y,z;
while(T--){
ans_max=ans_gmax=-inf;
scanf("%s",op);
if(op[0]=='Q') {
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",ans_max);
} else if(op[0]=='A') {
scanf("%d%d",&x,&y);
query(1,x,y);
printf("%d\n",ans_gmax);
} else if(op[0]=='P') {
scanf("%d%d%d",&x,&y,&z);
change(1,x,y,tag(z,-inf));
} else if(op[0]=='C') {
scanf("%d%d%d",&x,&y,&z);
change(1,x,y,tag(-inf,z));
}
}
return 0;
}