文章目录

1 #Segment_Tree
- 1.1 吉老师线段树

#Segment_Tree

吉老师线段树

题意就是说呢咱们要建一个线段树干甚呢？{维护区间加， 区间最值，区间求和，区间最值， 区间历史最值}

咱们先不考虑怎么维护历史最值问题，维护区间最值就是把 $A_i$ 变成 $min(A_i, v)$ ，那么快和我一起想暴力：怎么打暴力呢？搜！一直向下搜，搜到什么时候呢 $ l = r $ 或者 $ v > max $ ，$ max $ 为区间最大值，此时的复杂度就是 $ O (n ^ 2) $ ，看一眼数据： $ A_i \le 8 \times 10 ^ 8 $ 很显然，咱们接受不了，所以我们要考虑怎么对这个玩意儿进行维护。

吉老师在这里提出了一个比较好的解决办法：对于每一个结点，我们维护区间最大值，最大值的出现次数，区间严格次大值（用 $ sec $ 表示）。我们维护好了这些信息之后，我们发现我们可以在区间取 $min$ 操作时不断遍历线段树，直到 $ sec 如果对证明感兴趣，详见吉如一的讨论和灵梦的洛谷日报

那么，我们在加入了历史最值得操作后应该如何进行维护呢？详见 push_down 部分。

接下来的是三块内容： push_up， push_down，update_min。

数值上传（push_up）

我们可以直接上传区间最大值、历史最大值和区间和。但是怎么维护区间严格次大值和最大值出现次数呢？

我们先判断左右区间的最大值是否相同：如果相同，我们就把最有区间最大值出现的次数相加，并且取左右区间的严格次大值中较大的那个 $sec$ 最为该区间次大值；如果不同，取最大值较大的那个区间的最大值区间次数，并且将代取件的次大值于另一个区间的严格次大值进行比较，来更新该区间的次大值。

这部分其实蛮好理解的趴，上代码：

inline void push_up(int u){
    tree[u].maxa = max(tree[ls].maxa, tree[rs].maxa);
    tree[u].maxb = max(tree[ls].maxb, tree[rs].maxb);
    tree[u].sum = tree[ls].sum + tree[rs].sum;
    if(tree[ls].maxa == tree[rs].maxa){
        tree[u].sec = max(tree[ls].sec, tree[rs].sec);
        tree[u].cnt = tree[ls].cnt + tree[rs].cnt;
    }
    else if(tree[ls].maxa > tree[rs].maxa){
        tree[u].sec = max(tree[ls].sec, tree[rs].maxa);
        tree[u].cnt = tree[ls].cnt;
    }
    else{
        tree[u].sec = max(tree[ls].maxa, tree[rs].sec);
        tree[u].cnt = tree[rs].cnt;
    }
}

标记下传（push_down）

这里来讲一下我们加入历史最大值的操作应该如何进行维护。

首先呢我们需要维护的有四个 $tag$ ：$ add_a、 add_{a1}、 add_b、 add_{b1} $。

struct Seg{
    int add_a, add_a1, add_b, add_b1;
    int maxa, sec, maxb, sum, cnt, len;
}tree[N <<　3];

这里的四个 $tag$ 是用来做什么的呢？由于在吉老师线段树中，我们区间取 $min$ 的操作只会更新区间最大值的值，因此我们考虑将每个区间的数分为两类：最大数以及非最大数，再进行维护。这样我们在进行区间取 $min$ 时，就可以很方便地只对最大值进行操作了。因此，我们用 $ add_a， add_{a1} $ 分别表示当前区间最大值的加标记和当前区间非最大值的加标。至于啥子是加标，看这个。再用 $ add_b， add_{b1} $ 分别表示区间最大值历史上加的最多的那次的加标以及对应非最大值的加标。

什么叫做历史上加的最多的那次加标？我们来举一个例子，我们曾经给一个区间的最大值打上了 $ +1919810 $ 的加标记，然后我们进行一个操作，这个区间的最大值要 $-114514$ ，我们在打完这个标记哦之后， $ add_a $ 就变成了 $ +1805296 $，而 $ add_b $ 仍然是 $ +1919810 $。因为它在历史操作中加的最多的是 $1919810$ ，所以他的子区间在那一个操作的时刻是 $ +1919810 $ 的，并且只有在这个操作时，这个时刻才可能会是历史最大的位置。

OKEY，这四个标记咱们就算是明白了，那么后面的操作也就可以理解了。

由于嘞，标记下传老复杂了，咱通常就用 push_down 和 update 这两个操作来维护。对于 push_down ，我们先判断一下最大值在哪边，如果是左边，那么左边的最大值受到的影响就算是当前区间对最大值的影响，而右边的最大值收到的影响仅是当前区间对于次大值的影响罢了。（当然这个时候也会出现一种情况，那就是左右两边都有最大值，那么两边的最大值受到的影响均是当前区间对最大值的影响）那么第二种情况是最大值在右边，咱们反过来就行了~

inline void push_down(int u){
    int maxx = max(tree[ls].maxa, tree[rs].maxa);
    if(tree[ls].maxa == maxx) update(ls, tree[u].add_a, tree[u].add_b, tree[u].add_a1, tree[u].add_b1);
    else update(ls, tree[u].add_a1, tree[u].add_b1, tree[u].add_a1, tree[u].add_b1);
    if(tree[rs].maxa == maxx) update(rs, tree[u].add_a, tree[u].add_b, tree[u].add_a1, tree[u].add_b1);
    else update(rs, tree[u].add_a1, tree[u].add_b1, tree[u].add_a1, tree[u].add_b1);
    tree[u].add_a = tree[u].add_b = tree[u].add_a1 = tree[u].add_b1 = 0;
}

这时候，也许会有疑问吗？那就是，我们仅仅判断了当前的最大值在哪里，为什么我们的 $ add_b $ 也跟着走了，这个东西是用来维护历史值的啊，为什么会变掉啊？？？这个标记是当前最大值历史上加的最多的那次，那么也就是说，这个标记根本上是打给了当前最大值的，那么自然也就是和 $ add_a $ 是绑定在一起的，它动它也动。

之后一个操作是 $ upadte $ ，会有 $ x1， x2， x3， x4 $ 作为函数中的变量。

$x1， x2$ 分别要表示的是：当前 / 历史最大值要加的数。

$x3， x4$ 分别表示的是：当前 / 历史非最大值要加的数。

之后要做的就是更新每一个 $tag$ 。区间和是很好理解的，就是最大值加的标加上非最大值加的标。对于 $add_b$ ，它是历史上加的最多的那次的标，所以我们要做的是判断一下当前的 $ add_a $ 加上 $x1$ 是否会超过历史最大值，如果是，更新历史最大值。那么 $ add_{b1} $ 是类似的。对于我们的历史最大值，我们看看当前最大值加上历史上家的最多的时候加标记的值 $(x2)$ 是否超过了历史最大值，如果超过了，更新历史最大值，其他信息的维护就很简单了

inline void update(int u, int x1, int x2, int x3, int x4){
    tree[u].sum += x1 * tree[u].cnt + x3 * (tree[u].len - tree[u].cnt);
    tree[u].maxb = max(tree[u].maxb, tree[u].maxa + x2);
    tree[u].add_b = max(tree[u].add_b, tree[u].add_a + x2);
    tree[u].add_b1 = max(tree[u].add_b1, tree[u].add_a1 + x4);
    tree[u].maxa += x1;
    tree[u].add_a += x1;
    tree[u].add_a1 += x3;
    if(tree[u].sec != MIN) tree[u].sec += x3;
}

区间取最值

首先，如果该区间的最大值要比取得 $ v $ 小，显然直接返回即可。

接下来会有一种情况 $ sec \le v \le maxa $ ，那么我们就更新最大值。怎么更新呢？我们把 $maxa$ 变成了 $k$ ，也就是我们把最大值减去了 $maxa - v$ ，或者说，加了 $v - maxa$ ，那么这时我们用 $update$ 进行操作即可。若是不属于这两种情况中的任意一种，我们就要继续遍历到子区间。

inline void update_min(int u, int l, int r, int L, int R, int v){
    if(l > R || r < L || v >= tree[u].maxa) return;
    if(l >= L && r <= R && v >= tree[u].sec){
        update(u, v - tree[u].maxa, v - tree[u].maxa, 0, 0);
        return;
    }
    push_down(u);
    int mid = (l + r) >> 1;
    update_min(ls, l, mid, L, R, v);update_min(rs, mid + 1, r, L, R, v);
    push_up(u);
}

之后的函数其实和线段树1和线段树2中操作差不多就不说了

完整代码

#include<bits/stdc++.h>
#define int long long
#define ls u << 1
#define rs u << 1 | 1
#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)

const int N = 5e5 + 5;
const int MIN = -1e18;

using namespace std;

char buf[1 << 21],*p1 = buf,*p2 = buf;
template <typename T>
inline void read(T & r) {
    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();
    r = w ? - r : r;
}

struct Seg{
    int add_a, add_a1, add_b, add_b1;
    int maxa, sec, maxb, sum, cnt, len;
}tree[N];
int n, m, a[N];

inline void push_up(int u){
    tree[u].maxa = max(tree[ls].maxa, tree[rs].maxa);
    tree[u].maxb = max(tree[ls].maxb, tree[rs].maxb);
    tree[u].sum = tree[ls].sum + tree[rs].sum;
    if(tree[ls].maxa == tree[rs].maxa){
        tree[u].sec = max(tree[ls].sec, tree[rs].sec);
        tree[u].cnt = tree[ls].cnt + tree[rs].cnt;
    }
    else if(tree[ls].maxa > tree[rs].maxa){
        tree[u].sec = max(tree[ls].sec, tree[rs].maxa);
        tree[u].cnt = tree[ls].cnt;
    }
    else{
        tree[u].sec = max(tree[ls].maxa, tree[rs].sec);
        tree[u].cnt = tree[rs].cnt;
    }
}

inline void update(int u, int x1, int x2, int x3, int x4){
    tree[u].sum += x1 * tree[u].cnt + x3 * (tree[u].len - tree[u].cnt);
    tree[u].maxb = max(tree[u].maxb, tree[u].maxa + x2);
    tree[u].add_b = max(tree[u].add_b, tree[u].add_a + x2);
    tree[u].add_b1 = max(tree[u].add_b1, tree[u].add_a1 + x4);
    tree[u].maxa += x1;
    tree[u].add_a += x1;
    tree[u].add_a1 += x3;
    if(tree[u].sec != MIN) tree[u].sec += x3;
}

inline void push_down(int u){
    int maxx = max(tree[ls].maxa, tree[rs].maxa);
    if(tree[ls].maxa == maxx) update(ls, tree[u].add_a, tree[u].add_b, tree[u].add_a1, tree[u].add_b1);
    else update(ls, tree[u].add_a1, tree[u].add_b1, tree[u].add_a1, tree[u].add_b1);
    if(tree[rs].maxa == maxx) update(rs, tree[u].add_a, tree[u].add_b, tree[u].add_a1, tree[u].add_b1);
    else update(rs, tree[u].add_a1, tree[u].add_b1, tree[u].add_a1, tree[u].add_b1);
    tree[u].add_a = tree[u].add_b = tree[u].add_a1 = tree[u].add_b1 = 0;
}

inline void build(int u, int l, int r){
    tree[u].len = r - l + 1;
    if(l == r){
        tree[u].maxa = tree[u].maxb = tree[u].sum = a[l];
        tree[u].sec = MIN;tree[u].cnt = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);build(rs, mid + 1, r);
    push_up(u);
}

inline void update_add(int u, int l, int r, int L, int R, int k){
    if(l > R || r < L) return;
    if(l >= L && r <= R){
        update(u, k, k, k, k);
        return;
    }
    push_down(u);
    int mid = (l + r) >> 1;
    update_add(ls, l, mid, L, R, k);update_add(rs, mid + 1, r, L, R, k);
    push_up(u);
}

inline void update_min(int u, int l, int r, int L, int R, int v){
    if(l > R || r < L || v >= tree[u].maxa) return;
    if(l >= L && r <= R && v >= tree[u].sec){
        update(u, v - tree[u].maxa, v - tree[u].maxa, 0, 0);
        return;
    }
    push_down(u);
    int mid = (l + r) >> 1;
    update_min(ls, l, mid, L, R, v);update_min(rs, mid + 1, r, L, R, v);
    push_up(u);
}

inline int query_sum(int u, int l, int r, int L, int R){
    if(l > R || r < L) return 0;
    if(l >= L && r <= R) return tree[u].sum;
    int mid = (l + r) >> 1;
    push_down(u);
    return query_sum(ls, l, mid, L, R) + query_sum(rs, mid + 1, r, L, R);
}

inline int query_maxa(int u, int l, int r, int L, int R){
    if(l > R || r < L) return MIN;
    if(l >= L && r <= R) return tree[u].maxa;
    int mid = (l + r) >> 1;
    push_down(u);
    return max(query_maxa(ls, l, mid, L, R), query_maxa(rs, mid + 1, r, L, R));
}

inline int query_maxb(int u, int l, int r, int L, int R){
    if(l > R || r < L) return MIN;
    if(l >= L && r <= R) return tree[u].maxb;
    int mid = (l + r) >> 1;
    push_down(u);
    return max(query_maxb(ls, l, mid, L, R), query_maxb(rs, mid + 1, r, L, R));
}

signed main (){

    read(n);read(m);
    for(int i = 1; i <= n; i++) read(a[i]);

    build(1, 1, n);

    for(int i = 1; i <= m; i++){
        int opt, l, r, k;
        read(opt);read(l);read(r);
        if(opt == 1){
            read(k);
            update_add(1, 1, n, l, r, k);
        }
        else if(opt == 2){
            read(k);
            update_min(1, 1, n, l, r, k);
        }
        else if(opt == 3){
            printf("%lld\n", query_sum(1, 1, n, l, r));
        }
        else if(opt == 4){
            printf("%lld\n", query_maxa(1, 1, n, l, r));
        }
        else if(opt == 5){
            printf("%lld\n", query_maxb(1, 1, n, l, r));
        }
    }

    return 0;

}

Watertomato Blog

【Kacho】吉老师线段树

【Kacho】吉老师线段树

#Segment_Tree

吉老师线段树

数值上传（push_up）

标记下传（push_down）

区间取最值

完整代码

AT2063 [AGC005E] Sugigma: The Showdown 题解

CF1536D Omkar and Medians 题解

Kacho

叨叨几句... NOTHING

取消回复

Watertomato Blog