竞赛算法(7) 数据结构

并查集#

1
struct UfSet {
2
    int n;
3
    vector<int> pa, siz;
4

5
    void init(int _n = 0) {
6
        n = _n;
7
        pa.assign(_n, 0);
8
        iota(pa.begin(), pa.end(), 0);
9
        siz.assign(_n, 1);
10
    }
11

12
    UfSet(int _n = 0) { init(_n); }
13

14
    int find(int x) {
15
        while (x != pa[x]) {
16
            x = pa[x] = pa[pa[x]];
17
        }
18
        return x;
19
    }
20

21
    bool uni(int x, int y) {
22
        x = find(x), y = find(y);
23
        if (x == y) return false;
24
        if (siz[x] < siz[y]) swap(x, y);
25
        pa[y] = x;
26
        siz[x] += siz[y];
27
        return true;
28
    }
29
};

树状数组#

Fenwick tree 或者叫 Binary Indexed Tree, 功能类似于线段树, 只不过在差分操作的辅助下可以将空间压到 $O(n)$ , 并且代码简短, 常数小. 树状数组的索引通常从1开始. 树状数组只能维护满足结合律且可差分的数据和运算.

树状数组维护的运算必须满足群的性质.

树状数组和线段树作用的两个区别:

如果需要区间查询操作, 树状数组只能维护可差分信息(这一点可以通过维护两个树状数组来解决, 但时间复杂度升高)
树状数组修改操作使用的运算必须与维护信息的运算相同(或者说, 构成群结构), 而线段树不需要.(本质区别)

树状数组的性质
以下以c[i]代指i的管辖区间.

对于任意索引x, c[x]为[x - lowbit(x) + 1, x];

对于任意x <= y, 要么c[x]和c[y]不相交, 要么c[x]包含于c[y].

任意c[x]包含于c[x + lowbit(x)], 并且对于(x, x + lowbit(x))之间任意索引y, 都有c[y]与c[x]不相交.

在了解这些性质之后, 我们可以得到树状数组的单点修改和区间查询操作.

树状数组的区间查询操作
以下f[l, r]代表目标函数从l到r的区间和.

要查询f[l, r]时, 只需查询f[1, r] - f[1, l - 1];

要查询f[1, r]时: 初始令i = r, 然后每次让i -= lowbit(i)直到i == 0. 叠加所有的f[c[i]]即可.

树状数组的单点修改操作
假如要修改f[x].

修改f[c[x]].

令x = x + lowbit(x), 若x > n说明修改完毕, 否则重复步骤1.

1
inline int lowbit(int x) { return x & -x; }
2
template<typename S>
3
struct FwkTree {
4
    int n;
5
    vector<S> d;
6

7
    void init(int _n) { n = _n; d.assign(_n + 1, 0); }
8
    void init(const vector<S>& arr) {
9
        init(arr.size());
10
        for (int i = 1; i <= n; i++) {
11
            d[i] = arr[i - 1];
12
        }
13
        for (int i = 1; i <= n; i++) {
14
            int pa = i + lowbit(i);
15
            if (pa <= n) d[pa] += d[i];
16
        }
17
    }
18
    FwkTree(int n = 0) { init(n); }
19
    FwkTree(const vector<S>& arr) { init(arr); }
20

21
    void add(int x, S val) {
22
        for (int i = x + 1; i <= n; i += lowbit(i)) {
23
            d[i] += val;
24
        }
25
    }
26

27
    S sum(int x) {
28
        S ret = 0;
29
        for (int i = x + 1; i >= 1; i -= lowbit(i)) {
30
            ret += d[i];
31
        }
32
        return ret;
33
    }
34

35
    S sum(int l, int r) {
36
        // [l, r)
37
        return sum(r - 1) - sum(l - 1);
38
    }
39
};

权值树状数组#

其实就是把cnt数组存在树状数组里, 起了个高大上的名字.

这时其实我们就能查询大小在区间[L, R]里的数字个数了.

权值树状数组的核心用法: 查询索引在i左边/右边的数字中, 大小在某一区间内的数字个数. 也就是说, 假如数组是a[1], a[2], ..., a[n], 权值树状数组可以在 $O(n\log n)$ 内建树, 在 $O(\log n)$ 内查询i < q/i > p且a[i] >= L && a[i] <= R的a[i]数量.

有人就要问了, 既然需要 $O(n\log n)$ 的时间建树, 那我为什么不直接暴力 $O(n)$ 查找呢? 这是因为很多题目的查询是离线的, 这时我们可以把所有需要查询的i < q的问题按q的大小排好序, 这样建树的时候只需要从前往后建, 建到q_j的时候查询q_j处的问题, 只需要一次建树就能解决. 分摊复杂度 $O(\log n)$ .

SPOJ K-query(说白了就是查询[L, R]处满足>K的数字个数)

1
// 待补

树状数组上二分(倍增)#

1
// 树状数组上二分
2
namespace fwt_ext {
3
    // 查找权值树状数组上第k小元素的索引
4
    // 若总数不满k, 返回n
5
    // O(log n)
6
    template <class fwtree>
7
    int kth(const fwtree& fwk, ll k) {
8
        int n = fwk.n;
9
        assert(n > 0 && k > 0);
10
        if (n <= 0 || k <= 0) return -1;
11
        int pos = 0;
12
        int max_pow = 1 << (31 - __builtin_clz(n));
13
        for (int i = max_pow; i > 0; i >>= 1) {
14
            if (pos + i <= n && fwk.d[pos + i] < k) {
15
                k -= fwk.d[pos + i];
16
                pos += i;
17
            }
18
        }
19
        return pos;
20
    }
21

22
    // 采用倍增查找满足check(pref[i]) = true的最大下标i.
23
    // check 单调谓词函数[T, ..., T, F, ..., F], 返回0-based下的最大下标.
24
    // 若check(empty) = false, 返回-1
25
    template <class Monoid, typename F>
26
    int search(const FwkTree<Monoid>& fwk, F&& check) {
27
        using S = typename Monoid::value_type;
28
        int n = fwk.n;
29
        assert(n > 0);
30
        assert(check(Monoid::e()) == true);
31
        int pos = 0;
32
        int max_pow = 1 << (31 - __builtin_clz(n));
33
        S cur = Monoid::e();
34
        for (int i = max_pow; i > 0; i >>= 1) {
35
            if (pos + i <= n) {
36
                S next_val = Monoid::op(cur, fwk.d[pos + i]);
37
                if (check(next_val)) {
38
                    pos += i;
39
                    cur = next_val;
40
                }
41
            }
42
        }
43
        return pos - 1;
44
    }
45
}

区间加, 区间和#

显然, 树状数组可以在 $O(\log n)$ 的时间内实现单点修改和前缀和查询. 而我们发现如果用这个性质来维护差分数组的话, 单点修改其实就对应了原数组的区间修改, 前缀和就对应了原数组的单点值. 所以用树状数组来维护原数组的差分可以实现区间修改, 单点查询.

ST表#

1
// 稀疏表, Sparse Table.
2
// T为数据类型, op为一个函数指针, 默认产生区间最小值
3
template <typename T, T (*op)(T, T) = std::min>
4
struct SpTable {
5
    int n;
6
    int max_log;
7
    vector<vector<T>> st;
8

9
    SpTable(const vector<T>& a) : n(a.size()) {
10
        if (n == 0) return;
11
        max_log = 32 - __builtin_clz(n);
12
        st.assign(max_log, vector<T>(n));
13

14
        for (int i = 0; i < n; i++) st[0][i] = a[i];
15

16
        for (int j = 1; j < max_log; j++) {
17
            for (int i = 0; i + (1 << j) <= n; i++) {
18
                st[j][i] = op(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
19
            }
20
        }
21
    }
22

23
    // 查询区间 [l, r) 的结果: O(1)
24
    T prod(int l, int r) const {
25
        assert(0 <= l && l < r && r <= n);
26
        int j = 31 - __builtin_clz(r - l);
27
        return op(st[j][l], st[j][r - (1 << j)]);
28
    }
29
};

哈希表#

1
#include <ext/pb_ds/assoc_container.hpp>
2
#include <ext/pb_ds/tree_policy.hpp>
3
using __gnu_pbds::gp_hash_table;
4
using __gnu_pbds::null_type;
5
/*-------hashtable.hpp-------*/
6
// 防hack哈希表, 基于gp_hash_table, 速度快
7
// 支持整数类型作为键. 其他类型需先转换.
8
// 接口与unordered_set基本一致. 请注意最好不要使用count()
9
struct chash {
10
    // 你问我这堆数字是什么, 我也不知道
11
    static uint64_t splitmix64(uint64_t x) {
12
        x += 0x9e3779b97f4a7c15;
13
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
14
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
15
        return x ^ (x >> 31);
16
    }
17

18
    size_t operator()(uint64_t x) const {
19
        static const uint64_t FIXED_RANDOM =
20
            chrono::steady_clock::now().time_since_epoch().count();
21
        return splitmix64(x + FIXED_RANDOM);
22
    }
23
};
24
template<typename K, typename V>
25
using HashMap = gp_hash_table<K, V, chash>;
26
template<typename K>
27
using HashSet = gp_hash_table<K, null_type, chash>;

笛卡尔树#

1
// 笛卡尔树 (Cartesian Tree), 可以完全代替单调栈
2
// 默认 Compare = less<T> -> 大根堆 (Max-Tree) -> 维护区间最大值
3
template <typename T, typename Compare = std::less<T>>
4
struct CtsTree {
5
    int n;
6
    int root;
7
    vector<int> ltc, rtc; // 左右孩子, 分别代表管辖区间内左右的次大(小)值.
8
    vector<int> L, R;     // 管辖区间 [L, R] (闭区间)
9

10
    CtsTree(const vector<T>& a, Compare cmp = Compare()) : n(a.size()) {
11
        ltc.assign(n, -1);
12
        rtc.assign(n, -1);
13
        L.resize(n);
14
        R.resize(n);
15

16
        vector<int> stk;
17
        for (int i = 0; i < n; ++i) {
18
            L[i] = i;
19
            R[i] = i;
20
            int last_popped = -1;
21
            while (!stk.empty() && cmp(a[stk.back()], a[i])) {
22
                last_popped = stk.back();
23
                stk.pop_back();
24
            }
25
            if (last_popped != -1) {
26
                ltc[i] = last_popped;
27
            }
28
            if (!stk.empty()) {
29
                rtc[stk.back()] = i;
30
            }
31
            stk.push_back(i);
32
        }
33
        root = stk.empty() ? -1 : stk[0];
34
        if (root != -1) {
35
            init_range(root);   // 与建树复杂度一致
36
        }
37
    }
38

39
    // dfs预处理区间, O(n).
40
    void init_range(int u) {
41
        if (ltc[u] != -1) {
42
            init_range(ltc[u]);
43
            L[u] = L[ltc[u]];
44
        }
45
        if (rtc[u] != -1) {
46
            init_range(rtc[u]);
47
            R[u] = R[rtc[u]];
48
        }
49
    }
50

51
    // 返回 [l, r) 左闭右开区间 (0-based), 总贡献为((i + 1) - l)(r - i)
52
    // 即 [l, i + 1) 和 [i, r) 区间. O(1)
53
    pair<int, int> range(int i) const {
54
        return {L[i], R[i] + 1};
55
    }
56
};

线段树#

1
// 线段树(Segment Tree)
2
// Info 要求包含:
3
//     数据 = 空构造
4
//     friend Info operator+(const Info&, const Info&)
5
template<class Info>
6
struct SegTree {
7
    int n, size, log;
8
    vector<Info> d;
9
    void _pull(int x) {
10
        d[x] = d[x * 2] + d[x * 2 + 1];
11
    }
12

13
    // 对外接口
14
    // 重新建树
15
    void build(const vector<Info>& arr) {
16
        n = arr.size();
17
        log = 0;
18
        size = 1;
19
        while (size < n) {
20
            size *= 2;
21
            log++;
22
        }
23
        d.assign(2 * size, Info());
24
        for (int i = 0; i < n; i++) {
25
            d[size + i] = arr[i];
26
        }
27
        for (int i = size - 1; i > 0; i--) {
28
            _pull(i);
29
        }
30
    }
31

32
    SegTree(const vector<Info>& arr) {
33
        build(arr);
34
    }
35
    SegTree(int _n, const Info& def = Info()) {
36
        build(vector<Info>(_n, def));
37
    }
38

39
    // 单点赋值, O(log n)
40
    void set(int x, const Info& val) {
41
        assert(0 <= x && x < n);
42
        x += size;
43
        d[x] = val;
44
        // 自底向上更新，无需 push
45
        x /= 2;
46
        for (; x > 0; x /= 2) {
47
            _pull(x);
48
        }
49
    }
50

51
    // 区间查询[lt, rt), O(log n)
52
    Info query(int lt, int rt) {
53
        assert(0 <= lt && lt <= rt && rt <= n);
54
        if (lt == rt) {
55
            return Info();
56
        }
57
        if (lt + 1 == rt) {
58
            return d[size + lt];
59
        }
60
        lt += size;
61
        rt += size;
62
        Info sumlt, sumrt;
63
        for (; lt < rt; lt /= 2, rt /= 2) {
64
            if (lt % 2 == 1) {
65
                sumlt = sumlt + d[lt];
66
                lt++;
67
            }
68
            if (rt % 2 == 1) {
69
                rt--;
70
                sumrt = d[rt] + sumrt;
71
            }
72
        }
73
        return sumlt + sumrt;
74
    }
75

76
    // 扩展接口
77
    // 查最右rt使[lt, rt)满足check, O(log n)
78
    template <class F>
79
    int search_right(int lt, F check) {
80
        if (lt == n) {
81
            return n;
82
        }
83
        lt += size;
84
        Info sum;
85
        do {
86
            while (lt % 2 == 0) {
87
                lt /= 2;
88
            }
89
            if (!check(sum + d[lt])) {
90
                while (lt < size) {
91
                    lt *= 2;
92
                    if (check(sum + d[lt])) {
93
                        sum = sum + d[lt];
94
                        lt++;
95
                    }
96
                }
97
                return lt - size;
98
            }
99
            sum = sum + d[lt];
100
            lt++;
101
        } while (lowbit(lt) != lt);
102
        return n;
103
    }
104

105
    // 查最左lt使得[lt, rt)满足check, O(log n)
106
    template <class F>
107
    int search_left(int rt, F check) {
108
        if (rt == 0) {
109
            return 0;
110
        }
111
        rt += size;
112
        Info sum;
113
        do {
114
            rt--;
115
            while (rt > 1 && rt % 2 == 1) {
116
                rt /= 2;
117
            }
118
            if (!check(d[rt] + sum)) {
119
                while (rt < size) {
120
                    rt = 2 * rt + 1;
121
                    if (check(d[rt] + sum)) {
122
                        sum = d[rt] + sum;
123
                        rt--;
124
                    }
125
                }
126
                return rt + 1 - size;
127
            }
128
            sum = d[rt] + sum;
129
        } while (lowbit(rt) != rt);
130
        return 0;
131
    }
132
};

lazy tag版#

1
// 懒标记线段树(Lazy Segment Tree)
2
// Info 要求包含:
3
//     节点数据 = 空区间状态(零元)
4
//     void apply(const Tag&) 标记作用于数据
5
//     friend Info operator+(const Info&, const Info&)
6
// Tag 要求包含:
7
//     标记数据 = 叠加标记不变的状态(单位元)
8
//     void apply(const Tag&) 标记叠加
9
template<class Info, class Tag>
10
struct SegTree_lazy {
11
    int n, size, log;
12
    vector<Info> d;
13
    vector<Tag> tag;
14

15
    #define anc(x) ((x) >> i)
16
    #define ck(x) ((anc(x) << i) != x)
17
    void _pull(int x) {
18
        d[x] = d[x * 2] + d[x * 2 + 1];
19
    }
20
    void _apply(int x, const Tag& t) {
21
        d[x].apply(t);
22
        if (x < size) {
23
            tag[x].apply(t);
24
        }
25
    }
26
    void _push(int x) {
27
        _apply(x * 2, tag[x]);
28
        _apply(x * 2 + 1, tag[x]);
29
        tag[x] = Tag();
30
    }
31

32
    // 对外接口
33

34
    // 重新建树
35
    void build(const vector<Info>& arr) {
36
        n = arr.size();
37
        log = 0;
38
        size = 1;
39
        while (size < n) {
40
            size *= 2;
41
            log++;
42
        }
43
        d.assign(2 * size, Info());
44
        tag.assign(size, Tag());
45
        for (int i = 0; i < n; i++) {
46
            d[size + i] = arr[i];
47
        }
48
        for (int i = size - 1; i > 0; i--) {
49
            _pull(i);
50
        }
51
    }
52

53
    SegTree_lazy() : n(0) {}
54
    SegTree_lazy(const vector<Info>& arr) {
55
        build(arr);
56
    }
57
    SegTree_lazy(int _n, const Info& def = Info()) {
58
        build(vector<Info>(_n, def));
59
    }
60

61
    // 单点赋值, O(log n)
62
    void set(int x, const Info& val) {
63
        assert(0 <= x && x < n);
64
        x += size;
65
        for (int i = log; i > 0; i--) {
66
            _push(anc(x));
67
        }
68
        d[x] = val;
69
        for (int i = 1; i < log + 1; i++) {
70
            _pull(anc(x));
71
        }
72
    }
73

74
    // 区间修改[lt, rt), O(log n)
75
    void modify(int lt, int rt, const Tag& t) {
76
        assert(0 <= lt && lt <= rt && rt <= n);
77
        if (lt == rt) {
78
            return;
79
        }
80
        lt += size;
81
        rt += size;
82
        for (int i = log; i > 0; i--) {
83
            if (ck(lt)) {
84
                _push(anc(lt));
85
            }
86
            if (ck(rt)) {
87
                _push(anc(rt - 1));
88
            }
89
        }
90
        for (int i = lt, j = rt; i < j; i /= 2, j /= 2) {
91
            if (i % 2 == 1) {
92
                _apply(i, t);
93
                i++;
94
            }
95
            if (j % 2 == 1) {
96
                j--;
97
                _apply(j, t);
98
            }
99
        }
100
        for (int i = 1; i < log + 1; i++) {
101
            if (ck(lt)) {
102
                _pull(anc(lt));
103
            }
104
            if (ck(rt)) {
105
                _pull(anc(rt - 1));
106
            }
107
        }
108
    }
109

110
    // 区间查询[lt, rt)
111
    Info prod(int lt, int rt) {
112
        assert(0 <= lt && lt <= rt && rt <= n);
113
        if (lt == rt) {
114
            return Info();
115
        }
116
        lt += size;
117
        rt += size;
118
        for (int i = log; i > 0; i--) {
119
            if (ck(lt)) {
120
                _push(anc(lt));
121
            }
122
            if (ck(rt)) {
123
                _push(anc(rt - 1));
124
            }
125
        }
126
        Info sumlt, sumrt;
127
        for (; lt < rt; lt /= 2, rt /= 2) {
128
            if (lt % 2 == 1) {
129
                sumlt = sumlt + d[lt];
130
                lt++;
131
            }
132
            if (rt % 2 == 1) {
133
                rt--;
134
                sumrt = d[rt] + sumrt;
135
            }
136
        }
137
        return sumlt + sumrt;
138
    }
139

140
    // 扩展接口
141
    // 查最右rt使[lt, rt)满足check, O(log n)
142
    template <class F>
143
    int search_right(int lt, F check) {
144
        if (lt == n) {
145
            return n;
146
        }
147
        lt += size;
148
        for (int i = log; i > 0; i--) {
149
            _push(anc(lt));
150
        }
151
        Info sum;
152
        do {
153
            while (lt % 2 == 0) {
154
                lt /= 2;
155
            }
156
            if (!check(sum + d[lt])) {
157
                while (lt < size) {
158
                    _push(lt);
159
                    lt *= 2;
160
                    if (check(sum + d[lt])) {
161
                        sum = sum + d[lt];
162
                        lt++;
163
                    }
164
                }
165
                return lt - size;
166
            }
167
            sum = sum + d[lt];
168
            lt++;
169
        } while (lowbit(lt) != lt);
170
        return n;
171
    }
172

173
    // 查最左lt使得[lt, rt)满足check
174
    template <class F>
175
    int search_left(int rt, F check) {
176
        if (rt == 0) {
177
            return 0;
178
        }
179
        rt += size;
180
        for (int i = log; i > 0; i--) {
181
            _push(anc(rt - 1));
182
        }
183
        Info sum;
184
        do {
185
            rt--;
186
            while (rt > 1 && rt % 2 == 1) {
187
                rt /= 2;
188
            }
189
            if (!check(d[rt] + sum)) {
190
                while (rt < size) {
191
                    _push(rt);
192
                    rt = 2 * rt + 1;
193
                    if (check(d[rt] + sum)) {
194
                        sum = d[rt] + sum;
195
                        rt--;
196
                    }
197
                }
198
                return rt + 1 - size;
199
            }
200
            sum = d[rt] + sum;
201
        } while (lowbit(rt) != rt);
202
        return 0;
203
    }
204
    #undef anc
205
    #undef ck
206
};