封面来源

Pixiv 春を告げる-94945362

例题：P6242 【模板】线段树 3

题意：一颗线段树，可以维护区间加，区间取最值（），区间求和(，区间最大值，区间历史最值

吉老师提出了这样的解决方案：对于每一个节点，维护区间最大值，和最大值出现次数，区间严格次大值。在区间取操作时遍历线段树，直到,由于我们维护了区间最大值和次数，所以维护其他信息也就容易了。

修改经典线段树如下：

1.pushup

cpp
inline void pushup(int p){
    nd[p].mxa=max(nd[lc].mxa,nd[rc].mxa);
    nd[p].mxb=max(nd[lc].mxb,nd[rc].mxb);
    nd[p].sum=nd[lc].sum+nd[rc].sum;
    if(nd[lc].mxa==nd[rc].mxa){
        nd[p].sec=max(nd[lc].sec,nd[rc].sec);
        nd[p].cnt=nd[lc].cnt+nd[rc].cnt;
    }
    else if(nd[lc].mxa>nd[rc].mxa){
        nd[p].sec=max(nd[lc].sec,nd[rc].mxa);
        nd[p].cnt=nd[lc].cnt;
    }
    else{
        nd[p].sec=max(nd[lc].mxa,nd[rc].sec);
        nd[p].cnt=nd[rc].cnt;
    }
}

2.pushdown

感谢@Watertomato的讲解，维护四个 tag,，

表示当前区间最大值的 lazy_tag和非最大值的 lazy_tag,

同理,表示当前区间最大值的历史上加的最多的那次标记和非最大值的 历史上加的最多的那次标记

cpp
inline void pushdown(int p){
    int maxx=max(nd[lc].mxa,nd[rc].mxa);
    if(nd[lc].mxa==maxx)
        upd(lc,nd[p].add_a,nd[p].add_b,nd[p].add_a1,nd[p].add_b1);
    else upd(lc,nd[p].add_a1,nd[p].add_b1,nd[p].add_a1,nd[p].add_b1);
    if(nd[rc].mxa==maxx)
        upd(rc,nd[p].add_a,nd[p].add_b,nd[p].add_a1,nd[p].add_b1);
    else upd(rc,nd[p].add_a1,nd[p].add_b1,nd[p].add_a1,nd[p].add_b1);
    nd[p].add_a=nd[p].add_b=nd[p].add_a1=nd[p].add_b1=0;
}

3.update

cpp
inline void upd(int p,int k1,int k2,int k3,int k4){
    nd[p].sum+=k1*nd[p].cnt+k3*(nd[p].len-nd[p].cnt);
    nd[p].mxb=max(nd[p].mxb,nd[p].mxa+k2);
    nd[p].add_b=max(nd[p].add_b,nd[p].add_a+k2);
    nd[p].add_b1=max(nd[p].add_b1,nd[p].add_a1+k4);
    nd[p].mxa+=k1;
    nd[p].add_a+=k1;
    nd[p].add_a1+=k3;
    if(nd[p].sec!=-inf){
        nd[p].sec+=k3;
    }
}

表示当前/历史最大值要加的数。

表示非最大值要加的数。

4.update_min

cpp
inline void update_min(int p,int l,int r,int x,int y,int k){
    if(l>y||r<x||k>nd[p].mxa)return;
    if(l>=x&&r<=y&&k>=nd[p].sec){
        upd(p,k-nd[p].mxa,k-nd[p].mxa,0,0);
        return;
    }
    pushdown(p);
    update_min(lc,l,mid,x,y,k);
    update_min(rc,mid+1,r,x,y,k);
    pushup(p);
}

其他的和一般线段树没有区别了，直接看代码实现吧

cpp
#include<bits/stdc++.h>
#define inf 0x7fffffffffffff
#define FOR(i,l,r) for(register int i=l;i<=r;i++)
#define mid ((l+r)>>1)
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int N = 501000;int n,m;
struct STN{//segement nd node
    int add_a,add_a1,add_b,add_b1;
    int mxa,sec,mxb,sum,cnt,len;
}nd[N<<3];
inline int read();
int a[N];
inline void pushup(int);//
inline void build(int,int,int);//
inline void pushdown(int);//
inline void upd(int,int,int,int,int);//
inline void update_add(int,int,int,int,int,int);//
inline void update_min(int,int,int,int,int,int);//
inline int Qsum(int,int,int,int,int);//
inline int Qmxa(int,int,int,int,int);//
inline int Qmxb(int,int,int,int,int);//
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    #endif
    n=read(),m=read();
    FOR(i,1,n){
        a[i]=read();
    }
    build(1,1,n);
    for(int i=1,op,l,r,k;i<=m;i++){
        op=read();
        l=read();
        r=read();
        if(op==1){
            k=read();
            update_add(1,1,n,l,r,k);
        }
        else if(op==2){
            k=read();
            update_min(1,1,n,l,r,k);
        }
        else if(op==3){
            printf("%lld\n",Qsum(1,1,n,l,r));
        }
        else if(op==4){
            printf("%lld\n",Qmxa(1,1,n,l,r));
        }
        else if(op==5){
            printf("%lld\n",Qmxb(1,1,n,l,r));
        }
    }
 
}
inline int read() {
    int r=0;bool w=0; char ch=getchar();
    while(ch<'0'||ch>'9') w=ch=='-'?1:0,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+(ch^48), ch=getchar();
    return w?-r:r;
}
inline void pushup(int p){
    nd[p].mxa=max(nd[lc].mxa,nd[rc].mxa);
    nd[p].mxb=max(nd[lc].mxb,nd[rc].mxb);
    nd[p].sum=nd[lc].sum+nd[rc].sum;
    if(nd[lc].mxa==nd[rc].mxa){
        nd[p].sec=max(nd[lc].sec,nd[rc].sec);
        nd[p].cnt=nd[lc].cnt+nd[rc].cnt;
    }
    else if(nd[lc].mxa>nd[rc].mxa){
        nd[p].sec=max(nd[lc].sec,nd[rc].mxa);
        nd[p].cnt=nd[lc].cnt;
    }
    else{
        nd[p].sec=max(nd[lc].mxa,nd[rc].sec);
        nd[p].cnt=nd[rc].cnt;
    }
}
inline void build(int p,int l,int r){
    nd[p].len=r-l+1;
    if(l==r){
        nd[p].mxa=nd[p].mxb=nd[p].sum=a[l];
        nd[p].sec=-inf;
        nd[p].cnt=1;
        return;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(p);
}
inline void pushdown(int p){
    int maxx=max(nd[lc].mxa,nd[rc].mxa);
    if(nd[lc].mxa==maxx)
        upd(lc,nd[p].add_a,nd[p].add_b,nd[p].add_a1,nd[p].add_b1);
    else upd(lc,nd[p].add_a1,nd[p].add_b1,nd[p].add_a1,nd[p].add_b1);
    if(nd[rc].mxa==maxx)
        upd(rc,nd[p].add_a,nd[p].add_b,nd[p].add_a1,nd[p].add_b1);
    else upd(rc,nd[p].add_a1,nd[p].add_b1,nd[p].add_a1,nd[p].add_b1);
    nd[p].add_a=nd[p].add_b=nd[p].add_a1=nd[p].add_b1=0;
}
inline void upd(int p,int k1,int k2,int k3,int k4){
    nd[p].sum+=k1*nd[p].cnt+k3*(nd[p].len-nd[p].cnt);
    nd[p].mxb=max(nd[p].mxb,nd[p].mxa+k2);
    nd[p].add_b=max(nd[p].add_b,nd[p].add_a+k2);
    nd[p].add_b1=max(nd[p].add_b1,nd[p].add_a1+k4);
    nd[p].mxa+=k1;
    nd[p].add_a+=k1;
    nd[p].add_a1+=k3;
    if(nd[p].sec!=-inf){
        nd[p].sec+=k3;
    }
}
inline void update_add(int p,int l,int r,int x,int y,int k){
    if(l>y||r<x)return;
    if(l>=x&&r<=y){
        upd(p,k,k,k,k);
        return;
    }
    pushdown(p);
    update_add(lc,l,mid,x,y,k);
    update_add(rc,mid+1,r,x,y,k);
    pushup(p);
}
inline void update_min(int p,int l,int r,int x,int y,int k){
    if(l>y||r<x||k>nd[p].mxa)return;
    if(l>=x&&r<=y&&k>=nd[p].sec){
        upd(p,k-nd[p].mxa,k-nd[p].mxa,0,0);
        return;
    }
    pushdown(p);
    update_min(lc,l,mid,x,y,k);
    update_min(rc,mid+1,r,x,y,k);
    pushup(p);
}
inline int Qsum(int p,int l,int r,int x,int y){
    if(l>y||r<x)return 0;
    if(l>=x&&r<=y){
        return nd[p].sum;
    }
    pushdown(p);
    return Qsum(lc,l,mid,x,y)+Qsum(rc,mid+1,r,x,y);
}
inline int Qmxa(int p,int l,int r,int x,int y){
    if(l>y||r<x)return -inf;
    if(l>=x&&r<=y){
        return nd[p].mxa;
    }
    pushdown(p);
    return max(Qmxa(lc,l,mid,x,y),Qmxa(rc,mid+1,r,x,y));
}
inline int Qmxb(int p,int l,int r,int L,int R){
    if(l>R||r<L) return -1e18;
    if(l>=L&&r<=R) return nd[p].mxb;
    pushdown(p);
    return max(Qmxb(lc,l,mid,L,R),Qmxb(rc,mid+1,r,L,R));
}

后记

其实这篇文章完全可以算是搬运的。。。但好歹还是调了我一天的一道题，就当留个纪念吧.

参考资料

一篇背景诡异的ppt

有趣的线段树维护——吉老师线段树学习笔记

区间最值操作与区间历史最值详解 - 灵梦 的博客