线段树以及部分区间问题的板子

自从去年香港站因为没过线段树题而打铁第一次系统地重新认识线段树。

简介

线段树是一种维护含幺半群的数据结构（含幺半群就是包含幺元以及满足结合律的代数系统），因此线段树可以维护矩阵乘法。线段树上的每一个点都具有相同的性质，可以看作树的叶子是我们最开始所需处理的数据，而每向上一层，数据量减少一半，而所解出的值仍等价于最开始的数据，因此复杂度是$O(log)$。

能添加懒标记的线段树在线段树的基础上，还需满足下面几个点：懒标记能与线段树所需维护的量进行运算（后面会看到的mapping），懒标记之间能够进行运算（后面会看到的composition）

一般线段树

如上面所说的，这份板子中的$e$表示幺元，$f$表示求值的二元运算。 同时，这份板子中所维护的线段是$[l, r)$，在使用的时候需要注意。

 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

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647, mod = 998244353, MAXN = 1e5 + 10;
// [l, r)
template<typename T, typename F>
struct SegmentTree {
    int n;
    const F f;          // 二元运算
    const T e = T();    // 单位元
    vector<T> tree;
    SegmentTree(int n, F f) : n(n), tree(4 << __lg(n)), f(f) {}
    SegmentTree(vector<T> a, F f) : SegmentTree(a.size(), f) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if(r - l == 1) {
                tree[p] = a[l];
                return;
            }
            int m = l + r >> 1;
            build(p << 1, l, m), build(p << 1 | 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    };
    void pull(int p) {
        tree[p] = f(tree[p << 1], tree[p << 1 | 1]);
    }
    void modify(int p, int l, int r, int x, const T& v) {
        if(r - l == 1) {
            tree[p] = v;
            return;
        }
        int m = l + r >> 1;
        if(x < m) modify(p << 1, l, m, x, v);
        else modify(p << 1 | 1, m, r, x, v);
        pull(p);
    }
    T query(int p, int l, int r, int s, int t) {
        if(l >= t || r <= s) {
            return T();
        }
        if(l >= s && r <= t) {
            return tree[p];
        }
        int m = l + r >> 1;
        T res = f(query(p << 1, l, m, s, t), query(p << 1 | 1, m, r, s, t));
        return res;
    }
};
struct node {
    int v;
    node() : v(2147483647) {}
    node(int v) : v(v) {}
    bool operator<(const node& p) const{
        return v < p.v;
    }
};
auto f = [](node a, node b) {
    return min(a, b); 
};

void solve() {
    int n, q;
    cin >> n >> q;
    SegmentTree<node, decltype(f)> st(n + 1, f);
    while(q --) {
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 0) {
            st.modify(1, 0, n, x, node(y));
        } else {
            cout << st.query(1, 0, n, x, y + 1).v << '\n';
        }
    }
}

signed main () {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}

以上的代码是用来处理区间最小值的，若需要处理区间和，仅需做如下修改。

1
2
3
4
5
6
7
8

struct node {
    int v;
    node() : v(0) {}
    node(int v) : v(v) {}
};
auto f = [](node a, node b) {
    return node(a.v + b.v); 
};

接下来是线段树的一个变式——维护大于$0$的数据个数。代表应用就是扫描线。

下面的代码主要改动的部分就是修改，以及空间开大了一倍。

 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

#include <bits/stdc++.h>
using namespace std;
template<typename T, typename F>
struct SegmentTree {
    int n;
    const F f;          // 二元运算
    const T e = T();    // 单位元
    vector<T> tree;
    SegmentTree(int n, F f) : n(n), tree(8 << __lg(n)), f(f) {}
    SegmentTree(vector<T> a, F f) : SegmentTree(a.size(), f) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if(r - l == 1) {
                tree[p] = a[l];
                return;
            }
            int m = l + r >> 1;
            build(p << 1, l, m), build(p << 1 | 1, m, r);
            pull(p, l, r);
        };
        build(1, 0, n);
    };
    void pull(int p, int l, int r) {
        tree[p] = f(tree[p], tree[p << 1], tree[p << 1 | 1], l, r);
    }
    // 每次修改都需要数据pull一次进行数据更新
    void modify(int p, int l, int r, int s, int t, const int& v) {
        if(l >= t || r <= s) {
            return;
        }
        if(l >= s && r <= t) {
            tree[p].v += v;
            pull(p, l, r);
            return;
        }
        int m = l + r >> 1;
        modify(p << 1, l, m, s, t, v);
        modify(p << 1 | 1, m, r, s, t, v);
        pull(p, l, r);
    }
    T query(int p, int l, int r, int s, int t) {
        if(l >= t || r <= s) {
            return T();
        }
        if(l >= s && r <= t) {
            return tree[p];
        }
        int m = l + r >> 1;
        T res = f(query(p << 1, l, m, s, t), query(p << 1 | 1, m, r, s, t));
        return res;
    }
};
// 其中v是区间上元素的值，len表示区间上大于0的长度。
struct node {
    int v;
    int len;
    node() : v(0), len(0) {}
    node(int v, int len) : v(v), len(len) {}
};
auto f = [](node k, node a, node b, int l, int r) {
    if(r >= Y.size()) r --;
    return node(k.v, k.v ? r - l : a.len + b.len); 
};

添加懒标记的线段树

一些注记在上面的简介以及下面的注释都写了，就不再过多赘述。

  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

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef pair<int, int> PII;
const int INF = 2147483647, mod = 998244353, MAXN = 1e5 + 10;
// [l, r)
template<typename T, typename F, typename L, typename Map, typename Com>
struct Lazy_Segtre {
    int n;
    const F f;                  // 二元运算
    const T e  = T();           // 单位元
    const L e1 = L();           // 懒标记单位元
    const Map mapping;          // 解懒标记
    const Com composition;      // 添加(合并)懒标记
    vector<T> tree;
    vector<L> lazy;
    Lazy_Segtre(int n, F f, Map mapping, Com c) : n(n), tree(4 << __lg(n)), lazy(4 << __lg(n)), f(f), mapping(mapping), composition(c) {}
    Lazy_Segtre(vector<T> a, F f, Map m, Com c) : Lazy_Segtre(a.size(), f, m, c) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if(r - l == 1) {
                tree[p] = a[l];
                return;
            }
            int m = l + r >> 1;
            build(p << 1, l, m), build(p << 1 | 1, m, r);
            push_up(p);
        };
        build(1, 0, n);
    };
    void push_up(int p) {
        tree[p] = f(tree[p << 1], tree[p << 1 | 1]);
    }
    void push_down(int p, int l, int r) {
        tree[p] = mapping(tree[p], lazy[p], l, r);
        if(r - l > 1) {
            int m = l + r >> 1;
            lazy[p << 1] = composition(lazy[p << 1], lazy[p]);
            lazy[p << 1 | 1] = composition(lazy[p << 1 | 1], lazy[p]);
        }
        lazy[p] = e1;
    }
    void modify(int p, int l, int r, int s, int t, const L v) {
        push_down(p, l, r);
        if(l >= t || r <= s) {
            return;
        } 
        if(l >= s && r <= t) {
            lazy[p] = v;
            push_down(p, l, r);
            return;
        }
        int m = l + r >> 1;
        modify(p << 1, l, m, s, t, v);
        modify(p << 1 | 1, m, r, s, t, v);
        push_up(p);
    }
    T query(int p, int l, int r, int s, int t) {
        push_down(p, l, r);
        if(l >= t || r <= s) {
            return e;
        }
        if(l >= s && r <= t) {
            return tree[p];
        }
        int m = l + r >> 1;
        T res = f(query(p << 1, l, m, s, t), query(p << 1 | 1, m, r, s, t));
        return res;
    }
};
struct node {
    i64 v;
    node() : v(0) {}
    node(i64 v) : v(v) {}
    node& operator+= (const node& p) {
        v += p.v;
        return *this;
    }
};
struct Lazy : node {
    Lazy() : node() {}
    Lazy(int v) : node(v) {}
};
auto f = [&](node a, node b) {
    return node(a.v + b.v);
};
auto Map = [&](node a, Lazy b, int l, int r) {
    return node((r - l) * b.v + a.v);
};
auto Com = [&](Lazy a, Lazy b) {
    return Lazy(a.v + b.v);
};
void solve() {
    int n, q;
    cin >> n >> q;
    Lazy_Segtre<node, decltype(f), Lazy, decltype(Map), decltype(Com)> st(n, f, Map, Com);
    while(q --) {
        int op, x, y, z;
        cin >> op >> x >> y;
        x --, y --;
        if(op == 0) {
            cin >> z;
            st.modify(1, 0, n, x, y + 1, Lazy(z));
        } else {
            cout << st.query(1, 0, n, x, y + 1).v << '\n';
        }
    }
}

signed main () {
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
}

以上代码是区间加和求区间和，区间修改以及RMQ都是大同小异。

下面是区间修改，区间求和的所需做的修改。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

struct node {
    i64 v;
    node() : v(0) {}
    node(i64 v) : v(v) {}
};
struct Lazy : node {
    bool used;
    Lazy() : node(), used(false) {}
    Lazy(int v) : node(v), used(true) {}
};
auto f = [&](node a, node b) {
    return node(a.v + b.v);
};
auto Map = [&](node a, Lazy b, int l, int r) -> node {
    return node((b.used ? b.v * (r - l) : a.v));
};
auto Com = [&](Lazy a, Lazy b) {
    return (b.used ? b : a);
};

网络流细节

网络：

  • 带权有向图，含有源点s和汇点t

流（flow）：

  • 容量限制：$f(u, v) \leq c(u, v)$
  • 反对称性：$f(u, v) = f(v,u)$
  • 流量守恒：$\forall x \in V - {s, t}, \sum_{u, x} f(u, x) = \sum_{v, x} f(x, v)$，即对于任意一点，流入等于流出

剩余容量：

  • $c_f(u, v) = c(u, v) - f(u, v)$

残量网络：

  • 有剩余容量构成的网络，包括两部分内容：1. 原图边、2. 原图的反向边。
  • 残留网络记作$G_f$

增广路：

  • 残留网络上一条从$s$到$t$的路径。

退流：

  • 增量一条边的流量的同时要减少等量的反向边的流量。

最小割：

  • 如果在残量网络上找不到一条增广路，则说明已经求出了最大流/最小割，此时原图被分为$S-T$两个点集合，称为最小割，其中最小割的容量（$S$连向$T$的有向边权和）等于最大流；$S$连向$T$的边集成为最小割边集。

可行边：

  • $\exists$ 一个最小割边集 $E_s$, $e \subseteq E_s$。简单来说就是一条可行边属于所有最小割边集的并集。
  • 性质：
    1. 在某个最小割上满流，这是必要条件。
    2. 对于$e(u, v)$，残量网络上不存在另一条从$u$到$v$的路径（简言之就是重边）。 体现在图上就是$u$和$v$不在同一个$scc$中，因为反向边的存在，不满流的边相当于无向边，满流的边相当于没有边。

必须边：

  • $\forall$ 最小割边集 $E_s$, $e \subseteq E_s$。简单来说就是一条可行边属于所有最小割边集的交集。
  • 性质：
    1. 必须边 $\subseteq$ 可行边
    2. 在满足可行边的基础上，源点$s$和$u$属于同一个$scc$，汇点$t$和$v$属于同一个$scc$，直观上看就是从源点$bfs$找到的割边等于从汇点$bfs$找到的割边。

图的几个概念：

  • 匹配：
  • 边覆集：
  • 独立集：
  • 顶点覆集：

网络流题讲究对着限制找flow，对着代价找 cost。