Featured image of post 吉司机线段树

吉司机线段树

封面来源

Pixiv 春を告げる-94945362

例题P6242 【模板】线段树 3

题意:一颗线段树,可以维护区间加,区间取最值($A_i=min(A_i,v)$),区间求和($\sum_{i=l}^rA_i$,区间最大值,区间历史最值

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

修改经典线段树如下:

1.pushup

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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,$add_a,add_a1,add_b,add_b1$,

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
    }
}

$k1,k2$表示当前/历史最大值要加的数。

$k3,k4$表示非最大值要加的数。

4.update_min

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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);
}

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#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

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

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

所念皆星河
Built with Hugo
主题 StackJimmy 设计

提供全站CDN服务