segment tree beats

 

1.线段树维护历史最值

例题：洛谷P4314 CPU监控 

令 $(x,y)$ 标记表示将线段树当前区间所有数字变成 $\mathrm{max(a[i]+x, y)}$ 

通过 $(x,y)$ 标记可以实现区间赋值，区间加法，以及 $\mathrm{max(a[i]+x, y)}$   

在处理线段树标记的时候，要考虑标记如何结合在一起.  

对于标记 $(x,y)$ 与 $(x', y')$，按照顺序结合后的结果就是 $\mathrm{(x+x', max(y+x', y')}$.   

两个标记的结合是 $O(1)$ 的，故这种方法可以采用 pushdown 的方式进行下传.  

考虑如何处理历史最值.     

令历史最值标记 $(x,y)$ 表示可以令常数 $a$ 最大化的 $(x,y)$ 标记.  

父区间的标记被打上的时间显然晚于子区间标记被打上的时间，否则父区间的标记就被清空了.

假设子区间的当前最大值为 $\mathrm{nmax}$，当前标记为 $(x,y)$，父区间的历史最值标记为 $(x',y')$

新的最优历史最值标记显然可以是 $(x,y)$ 与 $(x',y')$ 的结合. 

对于常数 $a$ 的 $(x,y)$ 操作我们只会用到 $x,y$ 其中一个，所以历史最值标记中 $x,y$ 分别越大越好.

故上文子区间的历史最值标记就是原来的历史最值标记与新结合成的最值标记取 $\mathrm{max}$ 的结果.  

在下传标记的时候一定先下传历史最值标记，因为历史最值在下传时需要用到子节点的当前标记.  

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm> 
#define N 100007 
#define ll long long 
#define ls now<<1 
#define rs now<<1|1
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std; 
int n,Q;  
const int inf=(1<<30)-1;  
struct data {
    int x,y;  
    data(int a=0,int b=-inf) { x=a,y=b;}   
    data operator+(const data b) const {
        return data(max(-inf, x+b.x), max(y+b.x, b.y));  
    }
    data operator*(const data b) const {
        return data(max(x, b.x), max(y, b.y));  
    }
}ntag[N<<2],ptag[N<<2];  
int nmax[N<<2],pmax[N<<2];  
void pushup(int now) {
    nmax[now]=max(nmax[ls], nmax[rs]); 
    pmax[now]=max(pmax[ls], pmax[rs]);  
}
void build(int l,int r,int now) {
    ntag[now]=ptag[now]=data();  
    if(l==r) {
        scanf("%d",&nmax[now]); 
        pmax[now]=nmax[now];  
        return ;       
    }
    int mid=(l+r)>>1;  
    build(l, mid, ls); 
    build(mid+1, r, rs);  
    pushup(now);   
}
// 打当前标记.  
void markn(int now, data v) {
    ntag[now]=ntag[now]+v;      
    nmax[now]=max(nmax[now]+v.x, v.y);    
}     
void markp(int now, data v) {
    pmax[now]=max(pmax[now], max(nmax[now]+v.x, v.y));   
    ptag[now]=ptag[now]*(ntag[now]+v);   
}
void pushdown(int now) {
    markp(ls, ptag[now]); 
    markp(rs, ptag[now]); 
    markn(ls, ntag[now]); 
    markn(rs, ntag[now]); 
    ntag[now]=ptag[now]=data(); 
}
void update(int l,int r,int now,int L,int R,data v) {         
    if(l>=L&&r<=R) {    
        markp(now, v);   
        markn(now, v);  
        return ; 
    }
    pushdown(now); 
    int mid=(l+r)>>1;  
    if(L<=mid)  update(l, mid, ls, L, R, v); 
    if(R>mid)   update(mid+1, r, rs, L, R, v); 
    pushup(now);
}
int queryn(int l,int r,int now,int L,int R) {
    if(l>=L&&r<=R) return nmax[now]; 
    pushdown(now); 
    int mid=(l+r)>>1; 
    if(L<=mid&&R>mid) return max(queryn(l,mid,ls,L,R),queryn(mid+1,r,rs,L,R));  
    else if(L<=mid) return queryn(l,mid,ls,L,R); 
    else return queryn(mid+1,r,rs,L,R); 
}
int queryp(int l,int r,int now,int L,int R) {
    if(l>=L&&r<=R) return pmax[now]; 
    pushdown(now); 
    int mid=(l+r)>>1;  
    if(L<=mid&&R>mid) return max(queryp(l,mid,ls,L,R),queryp(mid+1,r,rs,L,R));  
    else if(L<=mid) return queryp(l,mid,ls,L,R); 
    else return queryp(mid+1,r,rs,L,R);  
}
int main() {
    // setIO("input");   
    scanf("%d",&n);  
    build(1, n, 1);  
    scanf("%d",&Q); 
    for(int i=1;i<=Q;++i) {    
        char op[2];  
        int l,r,z; 
        scanf("%s",op); 
        scanf("%d%d",&l,&r); 
        if(op[0]=='Q') printf("%d\n",queryn(1,n,1,l,r)); 
        if(op[0]=='A') printf("%d\n",queryp(1,n,1,l,r)); 
        if(op[0]=='P') scanf("%d",&z),update(1,n,1,l,r,data(z, -inf));  
        if(op[0]=='C') scanf("%d",&z),update(1,n,1,l,r,data(-inf, z));     
    }
    return 0; 
}