算法模版-数据结构

发表于 更新于 分类于 阅读次数： 本文字数： 26k
数据结构模版，慢慢更新。

数据结构

并查集

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
struct DSU {
    int n;
    std::vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            std::swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

带权并查集

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
struct DSU {
    int n;
    std::vector<int> p, sz, v;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        v.resize(n + 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        if (x == p[x]) {
            return x;
        }
        int o = p[x];
        p[x] = find(p[x]);
        v[x] += v[o];
        return p[x];
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        v[x] += sz[y];
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
    int query(int x) {
        find(x);
        return v[x];
    }
};

可撤销并查集

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
struct DSU {
    int n;
    std::vector<int> p, sz;
    std::vector<std::pair<int *, int>> stk;
    DSU() {}
    DSU(int n_) { init(n_); }
    void init(int n_) {
        n = n_;
        p.assign(n + 1, 0);
        iota(p.begin(), p.end(), 0);
        sz.assign(n + 1, 1);
        stk.clear();
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x];
        }
        return x;
    }

    void doit(int &x, int y) {
        stk.push_back({&x, x});
        x = y;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            std::swap(x, y);
        }
        doit(sz[y], sz[y] + sz[x]);
        doit(p[x], y);
        return true;
    }
    void roll(int cnt) {
        while (stk.size() > cnt) {
            auto [x, y] = stk.back();
            stk.pop_back();
            *x = y;
        }
    }
};

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct Fenwick {
    int n;
    std::vector<i64> a;
    Fenwick(int n = 0) { init(n); }
    void init(int n_) {
        n = n_;
        a.assign(n_ + 1, 0);
    }
    void add(int x, i64 v) {
        for (int i = x; i <= n; i += i & -i) {
            a[i] += v;
        }
    }
    i64 sum(int x) {
        i64 res = 0;
        for (int i = x; i >= 1; i -= i & -i) {
            res += a[i];
        }
        return res;
    }
    i64 rangeSum(int l, int r) { return sum(r) - sum(l - 1); }
};

权值树状数组

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
struct BIT {
    int n;
    std::vector<int> w;
    BIT(int n) {
        this->n = n;
        w.resize(n + 1);
    }
    void add(int x, int k) {
        for (; x <= n; x += x & -x) {
            w[x] += k;
        }
    }
    void add(int x, int y, int k) { add(x, k), add(y + 1, -k); }
    int ask(int x) {
        int ans = 0;
        for (; x; x -= x & -x) {
            ans += w[x];
        }
        return ans;
    }
    int ask(int x, int y) { return ask(y) - ask(x - 1); }
    int kth(int k) {  // 找第 k 小
        int ans = 0;
        for (int i = log2(n); i >= 0; i--) {
            int val = ans + (1 << i);
            if (val <= n && w[val] < k) {
                k -= w[val];
                ans = val;
            }
        }
        return ans + 1;
    }
    int get(int x) {  // 查找 x 排名
        int ans = 1;
        for (x--; x; x -= x & -x) {
            ans += w[x];
        }
        return ans;
    }
    int pre(int x) { return kth(get(x) - 1); }
    int suf(int x) { return kth(get(x + 1)); }
};

线段树（ 单点修改+区间合并）

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
template <class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 * (n + 1), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 * (n + 1), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    template <class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l > y || r < x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m + 1, r, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 1, n, l, r, pred);
    }
    template <class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l > y || r < x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (l == r) {
            return l;
        }
        int m = (l + r) / 2;
        int res = findLast(2 * p + 1, m + 1, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 1, n, l, r, pred);
    }
};

懒标记线段树

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
template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 * (n + 1), Info());
        tag.assign(4 * (n + 1), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);
                return;
            }
            int mid = (l + r) / 2;
            build(2 * p, l, mid);
            build(2 * p + 1, mid + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        if (x <= mid) {
            modify(2 * p, l, mid, x, v);
        } else {
            modify(2 * p + 1, mid + 1, r, x, v);
        }
        pull(p);
    }
  	void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (x <= l && r <= y) {
            return info[p];
        }
        push(p);
        int mid = (l + r) / 2;
        return rangeQuery(2 * p, l, mid, x, y) +
               rangeQuery(2 * p + 1, mid + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (x <= l && r <= y) {
            apply(p, v);
            return;
        }
        int mid = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, mid, x, y, v);
        rangeApply(2 * p + 1, mid + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        rangeApply(1, 1, n, l, r, v);
    }
    template <class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template <class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

ST 表

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
struct ST {
    const int n, k;
    std::vector<int> in1, in2;
    std::vector<std::vector<int>> Max, Min;
    ST(int n) : n(n), in1(n + 1), in2(n + 1), k(log2(n)) {
        Max.resize(k + 1, std::vector<int>(n + 1));
        Min.resize(k + 1, std::vector<int>(n + 1));
    }
    void init() {
        for (int i = 1; i <= n; i++) {
            Max[0][i] = in1[i];
            Min[0][i] = in2[i];
        }
        for (int i = 0, t = 1; i < k; i++, t *= 2) {
            const int T = n - t * 2 + 1;
            for (int j = 1; j <= T; j++) {
                Max[i + 1][j] = std::max(Max[i][j], Max[i][j + t]);
                Min[i + 1][j] = std::min(Min[i][j], Min[i][j + t]);
            }
        }
    }
    int getMax(int l, int r) {
        if (l > r) {
            std::swap(l, r);
        }
        int k = log2(r - l + 1);
        return std::max(Max[k][l], Max[k][r - (1 << k) + 1]);
    }
    int getMin(int l, int r) {
        if (l > r) {
            std::swap(l, r);
        }
        int k = log2(r - l + 1);
        return std::min(Min[k][l], Min[k][r - (1 << k) + 1]);
    }
};

主席树

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
struct PresidentTree {
    int cntNodes = 0;
    std::vector<int> root;

    struct node {
        int l = 0, r = 0;
        int val = 0, tag = 0;
    };

    std::vector<node> tr;

    PresidentTree(int n, int m) : root(m + 1), tr(21 * (n + m)), cntNodes(0) {}

  	// u，v传入参数是pt.root[i+1], pt.root[i]的形式
    void modify(int &u, int v, int l, int r, int x) {
        u = ++cntNodes;
        tr[u] = tr[v];
        tr[u].cnt++;
        if (l == r)
            return;
        int mid = (l + r) / 2;
        if (x <= mid)
            modify(tr[u].l, tr[v].l, l, mid, x);
        else
            modify(tr[u].r, tr[v].r, mid + 1, r, x);
    }
    // 找区间第k小
    int kth(int u, int v, int l, int r, int k) {
        if (l == r)
            return l;
        int res = tr[tr[v].l].cnt - tr[tr[u].l].cnt;
        int mid = (l + r) / 2;
        if (k <= res)
            return kth(tr[u].l, tr[v].l, l, mid, k);
        else
            return kth(tr[u].r, tr[v].r, mid + 1, r, k - res);
    }
  
    void build(int &u, int l, int r, const std::vector<int> &a) {
        u = ++cntNodes;
        if (l == r) {
            tr[u].val = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(tr[u].l, l, mid, a);
        build(tr[u].r, mid + 1, r, a);
        pull(u);
    }

    void pull(int p) { tr[p].val = tr[tr[p].l].val + tr[tr[p].r].val; }

    void rangeApply(int &u, int v, int l, int r, int x, int y, int val) {
        u = ++cntNodes;
        tr[u] = tr[v];
        tr[u].val += (std::min(r, y) - std::max(l, x) + 1) * val;
        if (x <= l && r <= y) {
            tr[u].tag += val;
            return;
        }
        int mid = (l + r) / 2;
        if (x <= mid) {
            rangeApply(tr[u].l, tr[v].l, l, mid, x, y, val);
        }
        if (mid < y) {
            rangeApply(tr[u].r, tr[v].r, mid + 1, r, x, y, val);
        }
    }

    int rangeQuery(int u, int l, int r, int x, int y, int mark = 0) {
        if (x <= l && r <= y) {
            return tr[u].val + mark * (r - l + 1);
        }
        int mid = (l + r) / 2;
        int res = 0;
        if (x <= mid)
            res += rangeQuery(tr[u].l, l, mid, x, y, mark + tr[u].tag);
        if (mid < y)
            res += rangeQuery(tr[u].r, mid + 1, r, x, y, mark + tr[u].tag);
        return res;
    }
};

线段树分治

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

std::vector<int> fa, dep;
std::vector<std::vector<int>> adj;
std::vector<std::array<int, 2>> e;
std::vector<int> ans;
std::vector<int> qry;
std::vector<bool> tag;

struct DSU {
    int n;
    std::vector<int> p, sz, val, up;
    std::vector<std::pair<int *, int>> stk;
    DSU() {}
    DSU(int n_) { init(n_); }
    void init(int n_) {
        n = n_;
        p.resize(n + 1);
        iota(p.begin(), p.end(), 0);
        sz.resize(n + 1, 1);
        sz[0] = 0;
        val.resize(n + 1);
        up.resize(n + 1);
        iota(up.begin(), up.end(), 0);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x];
        }
        return x;
    }

    void doit(int &x, int y) {
        stk.push_back({&x, x});
        x = y;
    }
    bool merge(int x, int y) {
        if (dep[x] < dep[y]) {
            std::swap(x, y);
        }
        x = find(x);
        y = find(y);
        doit(val[y], val[y] - sz[x]);
        int upy = up[y];
        if (upy > 1) {
            int z = find(fa[upy]);
            doit(val[z], val[z] + sz[x]);
        }
        if (sz[x] > sz[y]) {
            std::swap(x, y);
        }
        doit(up[y], upy);
        doit(sz[y], sz[y] + sz[x]);
        doit(val[y], val[y] + val[x]);
        doit(p[x], y);
        return true;
    }
    void roll(int cnt) {
        while (stk.size() > cnt) {
            auto [x, y] = stk.back();
            stk.pop_back();
            *x = y;
        }
    }
    int query(int x) {
        x = find(x);
        return sz[x] + val[x] + sz[find(fa[up[x]])];
    }
};

template <class Info>
struct SegmentTree {
    int q, n;
    std::vector<Info> info;
    DSU dsu;
    SegmentTree() : n(0) {}
    SegmentTree(int q_, int n_, Info v_ = Info()) { init(q_, n_, v_); }
    void init(int q_, int n_, Info v_ = Info()) {
        init(std::vector(q_ + 1, v_));
        n = n_;
        dsu.init(n);
    }
    template <class T>
    void init(std::vector<T> init_) {
        q = init_.size() - 1;
        info.assign(4 * (q + 1), Info());
    }
    void modify(int p, int l, int r, int x, int y, int v) {
        if (l > y || r < x) {
            return;
        }
        if (x <= l && r <= y) {
            info[p].e.push_back(v);
            return;
        }
        int mid = (l + r) / 2;
        modify(2 * p, l, mid, x, y, v);
        modify(2 * p + 1, mid + 1, r, x, y, v);
    }
    void modify(int l, int r, int v) { modify(1, 1, q, l, r, v); }
    void work(int p, int l, int r) {
        int sz = dsu.stk.size();
        for (auto id : info[p].e) {
            auto [x, y] = e[id];
            dsu.merge(x, y);
        }
        if (l == r) {
            if (tag[l]) {
                ans[l] = dsu.query(qry[l]);
            }
        } else {
            int mid = (l + r) / 2;
            work(2 * p, l, mid);
            work(2 * p + 1, mid + 1, r);
        }
        dsu.roll(sz);
    }
};

struct Info {
    std::vector<int> e;
    Info() {}
};

Info operator+(const Info &a, const Info &b) {
    Info info;
    info.e.insert(info.e.end(), a.e.begin(), a.e.end());
    info.e.insert(info.e.end(), b.e.begin(), b.e.end());
    return info;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;
    adj.resize(n + 1);
    e.resize(n);
    ans.resize(m + 1);
    tag.resize(m + 1);
    qry.resize(m + 1);
    fa.resize(n + 1);
    dep.resize(n + 1);
    std::map<int, int> mp;
    SegmentTree<Info> seg(m, n);
    for (int i = 1; i < n; i++) {
        int x, y, c;
        std::cin >> x >> y >> c;
        if (x > y) {
            std::swap(x, y);
        }
        adj[x].push_back(y);
        adj[y].push_back(x);
        e[i] = {x, y};
        if (c == 0) {
            mp[i] = 1;
        }
    }
    auto dfs = [&](auto dfs, int x) -> void {
        dep[x] = dep[fa[x]] + 1;
        for (auto y : adj[x]) {
            if (y == fa[x]) {
                continue;
            }
            fa[y] = x;
            seg.dsu.val[x]++;
            dfs(dfs, y);
        }
    };
    dfs(dfs, 1);
    for (int i = 1; i <= m; i++) {
        int op, x;
        std::cin >> op >> x;
        if (op == 1) {
            if (mp[x]) {
                if (i - 1 >= mp[x]) {
                    seg.modify(mp[x], i - 1, x);
                }
                mp[x] = 0;
            } else {
                mp[x] = i;
            }
        } else {
            tag[i] = true;
            qry[i] = x;
        }
    }
    for (int i = 1; i < n; i++) {
        if (mp[i]) {
            seg.modify(mp[i], m, i);
        }
    }
    seg.work(1, 1, m);
    for (int i = 1; i <= m; i++) {
        if (tag[i]) {
            std::cout << ans[i] << "\n";
        }
    }

    return 0;
}

树上启发式合并（dsu on tree）

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
#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<std::vector<int>> adj(n + 1);
    std::vector<int> color(n + 1);
    for (int i = 1; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        std::cin >> color[i];
    }
    std::vector<int> siz(n + 1), son(n + 1), L(n + 1), id(n + 1);
    int m;
    std::cin >> m;
    std::vector<int> qry(n + 1);
    int dfn = 0;
    auto dfs1 = [&](auto dfs1, int x, int fa) -> void {
        siz[x] = 1;
        L[x] = ++dfn;
        id[dfn] = x;
        for (auto y : adj[x]) {
            if (y == fa) {
                continue;
            }
            dfs1(dfs1, y, x);
            siz[x] += siz[y];
            if (siz[y] > siz[son[x]]) {
                son[x] = y;
            }
        }
    };
    dfs1(dfs1, 1, 0);
    std::vector<int> cnt(2e5 + 1);
    int ans = 0;
    auto add = [&](int x) {
        if (cnt[color[x]] == 0) {
            ans++;
        }
        cnt[color[x]]++;
    };
    auto del = [&](int x) {
        cnt[color[x]]--;
        if (cnt[color[x]] == 0) {
            ans--;
        }
    };
    auto dfs2 = [&](auto dfs2, int x, int fa, bool keep) -> void {
        for (auto y : adj[x]) {
            if (y == fa || y == son[x]) {
                continue;
            }
            dfs2(dfs2, y, x, false);
        }
        if (son[x]) {
            dfs2(dfs2, son[x], x, true);
        }
        for (auto y : adj[x]) {
            if (y == fa || y == son[x]) {
                continue;
            }
            for (int i = L[y]; i <= L[y] + siz[y] - 1; i++) {
                add(id[i]);
            }
        }
        add(x);
        qry[x] = ans;
        if (!keep) {
            for (int i = L[x]; i <= L[x] + siz[x] - 1; i++) {
                del(id[i]);
            }
        }
    };
    dfs2(dfs2, 1, 0, true);
    for (int i = 1; i <= m; i++) {
        int x;
        std::cin >> x;
        std::cout << qry[x] << "\n";
    }

    return 0;
}

单调栈

左边比自己大的第一个元素的位置——单调递增栈

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> a(n + 1);
std::vector<int> stk, pos(n + 1);
for (int i = 1; i <= n; i++) {
    while(!stk.empty() && a[i] >= a[stk.back()]) {
        stk.pop_back();
    }
    if(stk.empty()) {
        pos[i] = -1;
    } else {
        pos[i] = stk.back();
    }
    stk.push_back(i);
}

左边比自己小的第一个元素的位置——单调递减栈

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> a(n + 1);
std::vector<int> stk, pos(n + 1);
for (int i = 1; i <= n; i++) {
    while (!stk.empty() && a[i] <= a[stk.back()]) {
        stk.pop_back();
    }
    if (stk.empty()) {
        pos[i] = -1;
    } else {
        pos[i] = stk.back();
    }
    stk.push_back(i);
}

右边比自己大的第一个元素的位置——单调递增栈

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> a(n + 1);
std::vector<int> stk, pos(n + 1);
for (int i = n; i >= 1;i --) {
    while(!stk.empty() && a[i] >= a[stk.back()]) {
        stk.pop_back();
    }
    if(stk.empty()) {
        pos[i] = -1;
    } else {
        pos[i] = stk.back();
    }
    stk.push_back(i);
}

右边比自己小的第一个元素的位置——单调递减栈

1
2
3
4
5
6
7
8
9
10
11
12
13
std::vector<int> a(n + 1);
std::vector<int> stk, pos(n + 1);
for (int i = n; i >= 1;i --) {
    while(!stk.empty() && a[i] <= a[stk.back()]) {
        stk.pop_back();
    }
    if(stk.empty()) {
        pos[i] = -1;
    } else {
        pos[i] = stk.back();
    }
    stk.push_back(i);
}

单调队列

找长度为 k 的区间的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::deque<int> dq;
int pos = 1;
for (int i = k; i <= n; i++) {
    while (pos <= i) {
        while (!dq.empty() && a[pos] > a[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(pos);
        pos++;
    }
    while (!dq.empty() && i - dq.front() >= k) {
        dq.pop_front();
    }
    std::cout << a[dq.front()] << " \n"[i == n];
}

找长度为 k 的区间的最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
std::deque<int> dq;
int pos = 1;
for (int i = k; i <= n; i++) {
    while (pos <= i) {
        while (!dq.empty() && a[pos] < a[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(pos);
        pos++;
    }
    while (!dq.empty() && i - dq.front() >= k) {
        dq.pop_front();
    }
    std::cout << a[dq.front()] << " \n"[i == n];
}

平衡树 Treap

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
// 圆面积并
// 轮廓积分，复杂度 O(n^2logn)
// ans[i] 表示被至少覆盖了 i+1 次的区域的面积
vector<T> area_union(const vector<Circle> &circs) {
    const size_t siz = circs.size();
    using arc_t = tuple<Point, T, T, T>;
    vector<vector<arc_t>> arcs(siz);
    const auto eq = [](const arc_t &u, const arc_t &v) {
        const auto [u1, u2, u3, u4] = u;
        const auto [v1, v2, v3, v4] = v;
        return u1 == v1 && abs(u2 - v2) <= eps && abs(u3 - v3) <= eps &&
               abs(u4 - v4) <= eps;
    };

    auto cut_circ = [&](const Circle &ci, const size_t i) {
        vector<pair<T, int>> evt;
        evt.push_back({-PI, 0});
        evt.push_back({PI, 0});
        int init = 0;
        for (size_t j = 0; j < circs.size(); j++) {
            if (i == j) continue;
            const Circle &cj = circs[j];
            if (ci.r < cj.r - eps && ci.relation(cj) >= 3) init++;
            const auto inters = ci.inter(cj);
            if (inters.size() == 1)
                evt.push_back(
                    {atan2l((inters[0] - ci.c).y, (inters[0] - ci.c).x), 0});
            if (inters.size() == 2) {
                const Point dl = inters[0] - ci.c, dr = inters[1] - ci.c;
                T argl=atan2l(dl.y,dl.x),argr=atan2l(dr.y,dr.x);
                if (abs(argl+PI)<=eps) argl=PI;
                if (abs(argr+PI)<=eps) argr=PI;
                if (argl>argr+eps)
                {
                    evt.push_back({argl,1});
                    evt.push_back({PI, -1});
                    evt.push_back({-PI,1});
                    evt.push_back({argr, -1});
                }
                else
                {
                    evt.push_back({argl,1});
                    evt.push_back({argr,-1});
                }
            }
        }
        sort(evt.begin(),evt.end());
        int sum=init;
        for (size_t i=0;i<evt.size();i++)
        {
            sum+=evt[i].second;
            if (abs(evt[i].first-evt[i+1].first)>eps)
                arcs[sum].push_back(
                    {ci.c, ci.r, evt[i].first, evt[i + 1].first});
            if (abs(evt[i+1].first-PI)<=eps) break;
        }
    };

    const auto oint=[](const arc_t &arc)
    {
        const auto [cc,cr,l,r]=arc;
        if (abs(r-l-PI-PI)<=eps) return 2.0l*PI*cr*cr;
        return cr*cr*(r-l)+cc.x*cr*(sin(r)-sin(l))-cc.y*cr*(cos(r)-cos(l));
    };

    for (size_t i=0;i<circs.size();i++)
    {
        const auto &ci=circs[i];
        cut_circ(ci,i);
    }
    vector<T> ans(siz);
    for (size_t i=0;i<siz;i++)
    {
        T sum=0;
        sort(arcs[i].begin(),arcs[i].end());
        int cnt=0;
        for (size_t j=0;j<arcs[i].size();j++)
        {
            if (j>0 && eq(arcs[i][j],arcs[i][j-1])) arcs[i+(++cnt)].push_back(arcs[i][j]);
            else cnt=0,sum+=oint(arcs[i][j]);
        }
        ans[i]=sum/2;
    }
    return ans;
}

分块

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

void solve() {
    int n, q;
    cin >> n >> q;
    int sqn = sqrt(n);
    vector<int> st(sqn + 1), ed(sqn + 1), mark(sqn + 1), sz(sqn + 1);
    vector<vector<int>> v(sqn + 1);
    vector<int> a(n + 1), bel(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= sqn; i++) {
        st[i] = n / sqn * (i - 1) + 1;
        ed[i] = n / sqn * i;
    }
    ed[sqn] = n;
    for (int i = 1; i <= sqn; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;
            v[i].push_back(a[j]);
        }
        sort(v[i].begin(), v[i].end());
    }
    while (q--) {
        char op;
        int l, r, k;
        cin >> op >> l >> r >> k;
        if (op == 'M') {
            auto update = [&](int id) {
                int j = 0;
                for (int i = st[id]; i <= ed[id]; i++) {
                    v[id][j++] = a[i];
                }
                sort(v[id].begin(), v[id].end());
            };
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    a[i] += k;
                }
                update(bel[l]);
            } else {
                for (int i = l; i <= ed[bel[l]]; i++) {
                    a[i] += k;
                }
                update(bel[l]);
                for (int i = st[bel[r]]; i <= r; i++) {
                    a[i] += k;
                }
                update(bel[r]);
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    mark[i] += k;
                }
            }
        } else {
            int cnt = 0;
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    cnt += (mark[bel[i]] + a[i] >= k);
                }
            } else {
                for (int i = l; i <= ed[bel[l]]; i++) {
                    cnt += (mark[bel[i]] + a[i] >= k);
                }
                for (int i = st[bel[r]]; i <= r; i++) {
                    cnt += (mark[bel[i]] + a[i] >= k);
                }
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    cnt += (v[i].end() -
                            lower_bound(v[i].begin(), v[i].end(), k - mark[i]));
                }
            }
            cout << cnt << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 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
int n, q, k;
std::cin >> n >> q >> k;
std::vector<int> a(n + 1), pre(n + 1);
for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    pre[i] = pre[i - 1] ^ a[i];
}
std::vector<int> st(n + 1), ed(n + 1), bel(n + 1);
int sqn = sqrt(n);
for (int i = 1; i <= sqn; i++) {
    st[i] = n / sqn * (i - 1) + 1;
    ed[i] = n / sqn * i;
}
ed[sqn] = n;
for (int i = 1; i <= sqn; i++) {
    for (int j = st[i]; j <= ed[i]; j++) {
        bel[j] = i;
    }
}
std::vector<std::array<int, 3>> e(q + 1);
for (int i = 1; i <= q; i++) {
    int x, y;
    std::cin >> x >> y;
    x--;
    e[i] = {x, y, i};
}
std::sort(e.begin() + 1, e.end(), [&](auto &a, auto &b) {
    if (bel[a[0]] == bel[b[0]]) {
        return bel[a[0]] % 2 == 1 ? a[1] < b[1] : a[1] > b[1];
    }
    return a[0] < b[0];
});
std::vector<i64> res(q + 1);
std::vector<i64> cnt(1 << 22);
int l = 0, r = -1;
i64 ans = 0;
for (int i = 1; i <= q; i++) {
    auto [x, y, id] = e[i];
    auto add = [&](int x) {
        ans += cnt[pre[x] ^ k];
        cnt[pre[x]]++;
    };
    auto del = [&](int x) {
        cnt[pre[x]]--;
        ans -= cnt[pre[x] ^ k];
    };
    while (l > x) {
        add(--l);
    }
    while (r < y) {
        add(++r);
    }
    while (l < x) {
        del(l++);
    }
    while (r > y) {
        del(r--);
    }
    res[id] = ans;
}