Data Structures

DSU

普通并查集

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 {
    std::vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

种类并查集

用普通并查集开 $n \times k$ 倍空间， $k$ 为种类数。

trick

  1. 判断种类，关系。

    建边表示不同种类之间的关系。

  2. 判断无向图中是否有奇环（二分图充要条件）

    建边 $merge(x, y + n)$ ， $merge(x + n, y)$ ，如果 $same(x, y)$ 则图中有奇环。

带权并查集

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
struct DSU {
    std::vector<int> f, siz, val, max_val;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
        val.assign(n, 0);
        max_val.assign(n, 0);
    }

    int find(int x) {
        if (f[x] == x) {
            return x;
        }
        int t = find(f[x]);
        val[x] += val[f[x]]; // 计算权值
        return f[x] = t;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
    // x <- y 边权为 w
    bool merge(int x, int y, int w) {
        int vx = value(x);
        int vy = value(y);
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        max_val[x] = max(max_val[x], max_val[y] + vx - vy + w);
        val[y] += vx - vy + w;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }

    int value(int x) {
        find(x); // 路径压缩
        return val[x];
    }

    int max_value(int x) { // 连通块最大深度/权值
        return max_val[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
41
42
43
44
45
46
47
48
49
50
51
52
struct DSU {
    vector<int> f, siz;
    vector<pair<int, int>> stk;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    // O(log(n))
    int find(int x) { 
        while (x != f[x]) {
            x = f[x]; // 不能路径压缩
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) { // 按秩合并
            swap(x, y);
        }
        f[y] = x;
        siz[x] += siz[y];
        stk.push_back({ x, y });
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
    // 回退一步
    void undo() { 
        auto [x, y] = stk.back();
        stk.pop_back();
        siz[x] -= siz[y];
        f[y] = y;
    }
};

trick

  1. 维护连通块内的连通性，可以打 tag ，在并查集撤销时更新 tag 。merge 时要消除 tag 的影响。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (siz[x] < siz[y]) { // 按秩合并
            swap(x, y);
        }
        f[y] = x;
        siz[x] += siz[y];
        stk.push_back({ x, y });
        tag[y] -= tag[x]; // 消除 x 的影响
        return true;
    }
    // 回退一步
    void undo() { 
        auto [x, y] = stk.back();
        stk.pop_back();
        siz[x] -= siz[y];
        f[y] = y;
        tag[y] += tag[x]; // 标记传递
    }

Fenwick

Point set range query

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
template<class T>
struct Fenwick {
	int n;
	vector<T> sum;
	Fenwick(int _n = 0) {
		n = _n;
		sum.resize(n);
	}

	int lowbit(int x) {
		return x & (-x);
	}

	void update(int p, T k) {
		for (int i = p; i < n; i += lowbit(i)) {
			sum[i] += k;
		}
	}

	T prefixsum(int p) {
		T ans = 0;
		for (int i = p; i > 0; i -= lowbit(i)) {
			ans += sum[i];
		}
		return ans;
	}

	T rangesum(int l, int r) {
		return prefixsum(r) - prefixsum(l - 1);
	}
};

Jiangly

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
template <typename T>
struct Fenwick {
    int n;
    std::vector<T> a;
    
    Fenwick(int n_ = 0) {
        init(n_);
    }
    
    void init(int n_) {
        n = n_;
        a.assign(n, T{});
    }
    
    void add(int x, const T &v) {
        for (int i = x + 1; i <= n; i += i & -i) {
            a[i - 1] = a[i - 1] + v;
        }
    }
    
    T sum(int x) {
        T ans{};
        for (int i = x; i > 0; i -= i & -i) {
            ans = ans + a[i - 1];
        }
        return ans;
    }
    
    T rangeSum(int l, int r) {
        return sum(r) - sum(l);
    }
    
    int select(const T &k) {
        int x = 0;
        T cur{};
        for (int i = 1 << std::__lg(n); i; i /= 2) {
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        }
        return x;
    }
};

Range set range query

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
template<class T>
class Fenwick {
public:
	int N;
	vector<T> S;
	vector<T> C;
	Fenwick(int n = 0) {
		N = n;
		S.resize(N);
		C.resize(N);
	}

	int lowerbit(int x) {
		return x & (-x);
	}

	void update(int l, int r, T k) {
		Add(l, k);
		Add(r + 1, -k);
	}

	T query(int l, int r) {
		return Sum(r) - Sum(l - 1);
	}
private:
	void Add(int p, T k) {
		for (int i = p; i < N; i += lowerbit(i)) {
			S[i] += k;
			C[i] += k * p;
		}
	}

	T Sum(int p) {
		T Ssum = 0;
		T Csum = 0;
		for (int i = p; i > 0; i -= lowerbit(i)) {
			Ssum += S[i] * (p + 1);
			Csum += C[i];
		}
		return Ssum - Csum;
	}
};

二维树状数组

point set range query

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
template<class T>
struct Fenwick {
    int n, m;
    vector<vector<T>> val;
    Fenwick(int _n, int _m) {
        n = _n;
        m = _m;
        val.resize(n);
        for (int i = 0; i < n; i++) {
            val[i].resize(m);
        }
    }

    int lowbit(int x) {
        return x & (-x);
    }

    // 单点修改
    void add(int x, int y, T k) {
        for (int i = x; i < n; i += lowbit(i)) {
            for (int j = y; j < m; j += lowbit(j)) {
                val[i][j] += k;
            }
        }
    }

    T prefix(int x, int y) {
        T sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                sum += val[i][j];
            }
        }
        return sum;
    }

    T sum(int x1, int y1, int x2, int y2) {
        return prefix(x2, y2) - prefix(x2, y1 - 1) - prefix(x1 - 1, y2) + prefix(x1 - 1, y1 - 1);
    }
};

range set range query

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
template<class T>
struct Fenwick {
    int n, m;
    vector<vector<T>> a, b, c, d;
    Fenwick(int _n, int _m) {
        n = _n;
        m = _m;
        a.resize(n);
        b.resize(n);
        c.resize(n);
        d.resize(n);
        for (int i = 0; i < n; i++) {
            a[i].resize(m);
            b[i].resize(m);
            c[i].resize(m);
            d[i].resize(m);
        }
    }

    int lowbit(int x) {
        return x & (-x);
    }

    void add(int x1, int y1, int x2, int y2, T k) {
        update(x1, y1, k);
        update(x1, y2 + 1, -k);
        update(x2 + 1, y1, -k);
        update(x2 + 1, y2 + 1, k);
    } 

    void update(int x, int y, T k) {
        for (int i = x; i < n; i += lowbit(i)) {
            for (int j = y; j < m; j += lowbit(j)) {
                a[i][j] += k;
                b[i][j] += k * x;
                c[i][j] += k * y;
                d[i][j] += k * x * y;
            }
        }
    }

    T prefix(int x, int y) {
        T sum = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            for (int j = y; j > 0; j -= lowbit(j)) {
                sum += a[i][j] * (x + 1) * (y + 1);
                sum -= b[i][j] * (y + 1);
                sum -= c[i][j] * (x + 1);
                sum += d[i][j];
            }
        }
        return sum;
    }

    T sum(int x1, int y1, int x2, int y2) {
        return prefix(x2, y2) - prefix(x2, y1 - 1) - prefix(x1 - 1, y2) + prefix(x1 - 1, y1 - 1);
    }
};

Segment Tree

Point set range query

time:2024/3/22

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
struct Node {

    int lpos, rpos;
    // init
    Node() {

    }

    // update
    Node& operator+=(const Node& n) {

        return *this;
    }

    // push_up
    Node push_up(const Node& ln, const Node& rn) {

        return *this;
    }
};

struct SegmentTree {
    #define lp (p << 1)
    #define rp (p << 1 | 1)
    vector<Node> val;
    SegmentTree(int n = 0) {
        resize(n);
    }

    void resize(int n) {
        val.resize((n + 1) * 4);
    }

    void build(int l, int r, int p = 1) {
        val[p].lpos = l;
        val[p].rpos = r;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, lp);
        build(mid + 1, r, rp);
        val[p].push_up(val[lp], val[rp]);
    }

    void update(int pos, const Node& k, int p = 1) {
        if (val[p].lpos == pos && pos == val[p].rpos) {
            val[p] += k;
            return;
        }

        int mid = (val[p].lpos + val[p].rpos) >> 1;
        if (pos <= mid) {
            update(pos, k, lp);
        } else {
            update(pos, k, rp);
        }
        val[p].push_up(val[lp], val[rp]);
    }

    Node query(const int& l, const int& r, int p = 1) {
        if (l <= val[p].lpos && val[p].rpos <= r) {
            return val[p];
        }

        int mid = (val[p].lpos + val[p].rpos) >> 1;
        if (r <= mid) {
            return query(l, r, lp);
        }

        if (mid < l) {
            return query(l, r ,rp);
        }

        return Node().push_up(query(l, r, lp), query(l, r, rp));
    }
};

Range set range query

update:2024/3/14

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
struct Node {
    
    int lpos, rpos;
    Node() {

        lpos = 0;
        rpos = 0;
    }

    // update
    void operator+=(const Node& n) {

    }

    Node push_up(const Node& ln, const Node& rn) {

        return *this;
    }

    void push_down(Node& ln, Node& rn) {

    }
};

struct SegmentTree {
    #define lp (p << 1)
    #define rp (p << 1 | 1)
    vector<Node> val;
    SegmentTree(int n = 0) {
        resize(n);
    }

    void resize(int n) {
        val.resize((n + 1) * 4);
    }

    void build(int l, int r, int p = 1) {
        val[p].lpos = l;
        val[p].rpos = r;
        if (l == r) {// init
            return;
        }
        int mid = (val[p].lpos + val[p].rpos) >> 1;
        build(l, mid, lp);
        build(mid + 1, r, rp);
        val[p].push_up(val[lp], val[rp]);
    }

    void update(const int& l, const int& r, const Node& k, int p = 1) {
        if (l <= val[p].lpos && val[p].rpos <= r) {// update
            val[p] += k;
            return;
        }
        val[p].push_down(val[lp], val[rp]);
        int mid = (val[p].lpos + val[p].rpos) >> 1;
        if (l <= mid) {
            update(l, r, k, lp);
        }
        if (mid < r) {
            update(l, r, k, rp);
        }
        val[p].push_up(val[lp], val[rp]);
    }

    Node query(const int& l, const int& r, int p = 1) {
        if (l <= val[p].lpos && val[p].rpos <= r) {
            return val[p];
        }
        val[p].push_down(val[lp], val[rp]);
        int mid = (val[p].lpos + val[p].rpos) >> 1;
        if (r <= mid) {
            return query(l, r, lp);
        }
        if (mid < l) {
            return query(l, r, rp);
        }
        return Node().push_up(query(l, r, lp), query(l, r, rp));
    }
};

LazySegmentTree

update:2024/6/21

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
struct Node {
    int begin;
    int end;
    Node() : info(this) {}
    struct Tag {
        Tag() {}
        void apply(const Tag& t) {}
    } tag;
    struct Info {
        Node* node;
        Info(Node* node = nullptr) : node(node) {}
        template<class T = Info>
        Info operator=(const T& info) { return *this; }
        void apply(const Tag& t) {}
        Info push(const Info& a, const Info& b) { return *this; }
    } info;
};

struct LazySegmentTree {
    int n;
    vector<Node> node;
    template<class T = Node::Info>
    LazySegmentTree(const vector<T>& val) {
        init(val);
    }
    template<class T = Node::Info>
    LazySegmentTree(int n, T v) {
        init(vector(n, v));
    }
    template<class T = Node::Info>
    void init(const vector<T>& val) {
        n = val.size();
        node.resize(4 << __lg(n));
        function<void(int, int, int)> build = [&](int begin, int end, int p) -> void {
            this->begin(p) = begin;
            this->end(p) = end;
            if (end - begin == 1) {
                info(p) = val[begin];
                return;
            }
            int middle = (begin + end) / 2;
            build(begin, middle, left(p));
            build(middle, end, right(p));
            push_up(p);
        };
        build(0, n, 1);
    }
    int& begin(const int& p) {
        return node[p].begin;
    }
    int& end(const int& p) {
        return node[p].end;
    }
    Node::Tag& tag(const int& p) {
        return node[p].tag;
    }
    Node::Info& info(const int& p) {
        return node[p].info;
    }
    int left(const int& p) const {
        return p * 2;
    }
    int right(const int& p) const  {
        return p * 2 + 1;
    }
    void push_up(const int& p) {
        info(p).push(info(left(p)), info(right(p)));
    }
    void apply(const int& p, const Node::Tag& t) {
        info(p).apply(t);
        tag(p).apply(t);
    }
    void push_down(const int& p) {
        apply(left(p), tag(p));
        apply(right(p), tag(p));
        tag(p) = Node::Tag();
    }
    void modify(const int& pos, const Node::Info& i, const int& p = 1) {
        if (end(p) - begin(p) == 1) {
            info(p) = i;
            return;
        }
        int middle = (begin(p) + end(p)) / 2;
        push_down(p);
        if (pos < middle) {
            modify(pos, i, left(p));
        } else {
            modify(pos, i, right(p));
        }
        push_up(p);
    }
    void rangeApply(const int& l, const int& r, const Node::Tag& t, const int& p = 1) {
        if (end(p) <= l || r <= begin(p)) {
            return;
        }
        if (l <= begin(p) && end(p) <= r) {
            return apply(p, t);
        }
        push_down(p);
        rangeApply(l, r, t, left(p));
        rangeApply(l, r, t, right(p));
        push_up(p);
    }
    template<class Error, class Ok>
    void rangeApply(const int& l, const int& r, const Node::Tag& t, const Error& error, const Ok& ok, const int& p = 1) {
        if (error(node[p], l, r, t)) {
            return;
        }
        if (ok(node[p], l, r, t)) {
            return apply(p, t);
        }
        push_down(p);
        rangeApply(l, r, t, error, ok, left(p));
        rangeApply(l, r, t, error, ok, right(p));
        push_up(p);
    }
    Node::Info rangeQuery(const int& l, const int& r, const int& p = 1) {
        if (end(p) <= l || r <= begin(p)) {
            return Node::Info();
        }
        if (l <= begin(p) && end(p) <= r) {
            return info(p);
        }
        push_down(p);
        return Node::Info().push(rangeQuery(l, r, left(p)), rangeQuery(l, r, right(p)));
    }
};

range add range multiply

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
int Mod;
struct Node {
    int begin;
    int end;
    Node() : info(this) {}
    struct Tag {
        long long add;
        long long mul;
        Tag() {
            add = 0;
            mul = 1;
        }
        void apply(const Tag& t) {
            add = (add * t.mul + t.add) % Mod;
            mul = mul * t.mul % Mod;
        }
    } tag;
    struct Info {
        Node* node;
        long long val;
        Info(Node* node = nullptr) : node(node) {
            val = 0;
        }
        template<class T = Info>
        Info operator=(const T& info) {
            val = info;
            return *this;
        }
        void apply(const Tag& t) {
            val = (val * t.mul + t.add * (node->end - node->begin)) % Mod;
        }
        Info push(const Info& a, const Info& b) {
            val = (a.val + b.val) % Mod;
            return *this;
        }
    } info;
};

range add range min range max

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
constexpr long long inf = 1e18;

struct Node {
    int begin;
    int end;
    Node() : info(this) {}
    struct Tag {
        long long add;
        long long max;
        long long min;
        Tag() {
            add = 0;
            max = -inf;
            min = inf;
        }
        void apply(const Tag& t) {
            if (t.add != 0) { // add
                add += t.add;
                if (max != -inf) max += t.add;
                if (min != inf)  min += t.add;
            }
            if (t.max != -inf) { // max
                min = std::max(min, t.max);
                max = std::max(max, t.max);
            }
            if (t.min != inf) { // min
                max = std::min(max, t.min);
                min = std::min(min, t.min);
            }
        }
    } tag;
    struct Info {
        Node* node;
        long long max;
        long long maxCnt;
        long long secMax;
        long long min;
        long long minCnt;
        long long secMin;
        long long sum;
        Info(Node* node = nullptr) : node(node) {
            max = -inf;
            maxCnt = 0;
            secMax = -inf;
            min = inf;
            minCnt = 0;
            secMin = inf;
            sum = 0;         
        }
        template<class T = Info>
        Info operator=(const T& info) {
            max = info;
            maxCnt = 1;
            min = info;
            minCnt = 1;
            sum = info;
            return *this;
        }
        void apply(const Tag& t) {
            const int& begin = node->begin;
            const int& end = node->end;
            if (t.add != 0) { // add
                max += t.add;
                if (secMax != -inf) secMax += t.add;
                min += t.add;
                if (secMin != inf) secMin += t.add;
                sum += t.add * (end - begin);
            }
            if (t.max > min) { // max
                sum += (t.max - min) * minCnt;
                if (secMax == min)  secMax = t.max;
                if (max == min) max = t.max;
                min = t.max;
            }
            if (t.min < max) { // min
                sum += (t.min - max) * maxCnt;
                if (secMin == max) secMin = t.min;
                if (min == max) min = t.min;
                max = t.min;
            }
        }
        Info push(const Info& a, const Info& b) {
            max = std::max(a.max, b.max);
            if (a.max == b.max) {
                maxCnt = a.maxCnt + b.maxCnt;
                secMax = std::max(a.secMax, b.secMax);
            } else {
                if (a.max > b.max) {
                    maxCnt = a.maxCnt;
                    secMax = std::max(a.secMax, b.max);
                } else {
                    maxCnt = b.maxCnt;
                    secMax = std::max(a.max, b.secMax);
                }
            }
            min = std::min(a.min, b.min);
            if (a.min == b.min) {
                minCnt = a.minCnt + b.minCnt;
                secMin = std::min(a.secMin, b.secMin);
            } else {
                if (a.min < b.min) {
                    minCnt = a.minCnt;
                    secMin = std::min(a.secMin, b.min);
                } else {
                    minCnt = b.minCnt;
                    secMin = std::min(a.min, b.secMin);
                }
            }
            sum = a.sum + b.sum;
            return *this;
        }
    } info;
};

auto maxError = [](const Node& node, const int& l, const int& r, const Node::Tag& t) -> bool {
    return node.end <= l || r <= node.begin || node.info.min >= t.max;
};
auto maxOk = [](const Node& node, const int& l, const int& r, const Node::Tag& t) -> bool {
    return l <= node.begin && node.end <= r && node.info.secMin > t.max;
};
auto minError = [](const Node& node, const int& l, const int& r, const Node::Tag& t) -> bool {
    return node.end <= l || r <= node.begin || node.info.max <= t.min;
};
auto minOk = [](const Node& node, const int& l, const int& r, const Node::Tag& t) -> bool {
    return l <= node.begin && node.end <= r && node.info.secMax < t.min;
};

President Tree

1

LiChaoSegmentTree

维护从 $x$ 处往下看最高的点，以及它的最小 $id$

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
constexpr double eps = 1e-9;

int cmp(double x, double y) {
    if (x - y > eps) return 1;
    if (y - x > eps) return -1;
    return 0;
}

constexpr double inf = 1e18;

struct Line {
    int id;
    double k, b;
    Line() {
        id = 0;
        k = 0;
        b = -inf;
    }
    Line(double x1, double y1, double x2, double y2) {
        if (cmp(x1, x2) == 0) { // 斜率不存在
            k = 0;
            b = max(y1, y2);
        } else {
            k = (y2 - y1) / (x2 - x1);
            b = y1 - k * x1;
        }
    }
    double get(double x) {
        return k * x + b;
    }
};

struct Node {
    Line line; // 该区间最优线段
    int lpos, rpos;
};

struct LiChaoSegmentTree {
    #define lp (p << 1)
    #define rp (p << 1 | 1)
    vector<Node> node;
    LiChaoSegmentTree(int left, int right) {
        int n = right - left + 1;
        node.resize(n * 4);
        function<void(int, int, int)> build = [&](int l, int r, int p) -> void {
            node[p].lpos = l;
            node[p].rpos = r;
            if (l == r) {
                return;
            }
            int m = (l + r) >> 1;
            build(l, m, lp);
            build(m + 1, r, rp);
        };
        build(left, right, 1);
    }

    void update(int l, int r, Line line, int p = 1) {
        int mid = (node[p].lpos + node[p].rpos) >> 1;
        if (l <= node[p].lpos && node[p].rpos <= r) {
            if (cmp(line.get(mid), node[p].line.get(mid)) == 1) {
                swap(line, node[p].line);
            }
            if (cmp(line.get(node[p].lpos), node[p].line.get(node[p].lpos)) == 1 || 
                (cmp(line.get(node[p].lpos), node[p].line.get(node[p].lpos)) == 0 && line.id < node[p].line.id)) {
                update(l, r, line, lp);
            }
            if (cmp(line.get(node[p].rpos), node[p].line.get(node[p].rpos)) == 1 || 
                (cmp(line.get(node[p].rpos), node[p].line.get(node[p].rpos)) == 0 && line.id < node[p].line.id)) {
                update(l, r, line, rp);
            }
            return;
        }
        if (l <= mid) {
            update(l, r, line, lp);
        } 
        if (mid < r) {
            update(l, r, line, rp);
        }
    }

    Line query(int x, int p = 1) {
        if (node[p].lpos == node[p].rpos) {
            return node[p].line;
        }
        Line res = node[p].line;
        int mid = (node[p].lpos + node[p].rpos) >> 1;
        Line temp = x <= mid ? query(x, lp) : query(x, rp);
        if (cmp(res.get(x), temp.get(x)) == -1 || 
            (cmp(res.get(x), temp.get(x)) == 0 && res.id > temp.id)) {
            res = temp;
        }
        return res;
    }
};

维护从 $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
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
constexpr double eps = 1e-9;
constexpr double inf = 1e18;

int cmp(double x, double y) {
    if (x - y > eps) return 1;
    if (y - x > eps) return -1;
    return 0;
}

struct Line {
    double k, b;
    Line() : k(0), b(-inf) {}
    double get(double x) const {
        return k * x + b;
    }
    friend bool better(const Line& left, const Line& right, double x) {
        return cmp(left.get(x), right.get(x)) == 1; 
    }
};

struct Node {
    Line line;
    int lpos, rpos;
};

struct LiChaoSegmentTree {
    #define lp (p << 1)
    #define rp (p << 1 | 1)
    vector<Node> node;
    LiChaoSegmentTree(int left, int right) {
        int n = right - left + 1;
        node.resize(n * 4);
        function<void(int, int, int)> build = [&](int l, int r, int p) -> void {
            node[p].lpos = l;
            node[p].rpos = r;
            if (l == r) {
                return;
            }
            int m = (l + r) >> 1;
            build(l, m, lp);
            build(m + 1, r, rp);
        };
        build(left, right, 1);
    }

    void update(int l, int r, Line line, int p = 1) {
        int mid = (node[p].lpos + node[p].rpos) >> 1;
        if (l <= node[p].lpos && node[p].rpos <= r) {
            if (better(line, node[p].line, mid)) swap(line, node[p].line);
            if (better(line, node[p].line, node[p].lpos)) update(l, r, line, lp);
            if (better(line, node[p].line, node[p].rpos)) update(l, r, line, rp);
            return;
        }
        if (l <= mid) update(l, r, line, lp);
        if (mid < r) update(l, r, line, rp);
    }

    Line query(int x, int p = 1) {
        if (node[p].lpos == node[p].rpos) {
            return node[p].line;
        }
        Line res = node[p].line;
        int mid = (node[p].lpos + node[p].rpos) >> 1;
        Line ans = x <= mid ? query(x, lp) : query(x, rp);
        if (not better(res, ans, x)) {
            swap(res, ans);
        } 
        return res;
    }
};

SegmentTree-Divide

线段树分治 + DSU

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
struct Info {
    int x, y;
};

struct Node {
    vector<Info> info; // 在 [lpos, rpos] 时间点存在边 x, y
    int lpos, rpos;
    // init
    Node() {}
    Node(Info i) {
        info.push_back(i);
    }

    // insert
    Node& operator+=(const Info& i) {
        this->info.push_back(i);
        return *this;
    }
};

struct SegmentTree {
    #define lp (p << 1)
    #define rp (p << 1 | 1)
    int n;
    DSU dsu;
    vector<int> ans;
    vector<Node> node;
    SegmentTree(int n = 0) {
        resize(n);
    }

    void resize(int n) {
        this->n = n;
        dsu.init((n + 1) * 2 + 1);
        ans.resize(n + 1);
        node.resize((n + 1) * 4);
    }

    void build(int l, int r, int p = 1) {
        node[p].lpos = l;
        node[p].rpos = r;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, lp);
        build(mid + 1, r, rp);
    }

    void insert(int l, int r, const Info& info, int p = 1) {
        if (l <= node[p].lpos && node[p].rpos <= r) {
            node[p] += info;
            return;
        }
        int mid = (node[p].lpos + node[p].rpos) / 2;
        if (l <= mid) insert(l, r, info, lp);
        if (mid < r)  insert(l, r, info, rp);
    }

    void solve(int p = 1) {
        // 计算
        bool flag = true;
        int top = dsu.stk.size();
        for (auto& [x, y] : node[p].info) {
            if (dsu.same(x, y)) {
                for (int i = node[p].lpos; i <= node[p].rpos; i++) {
                    ans[i] = false;
                }
                flag = false;
                break;
            }
            dsu.merge(x, y + n);
            dsu.merge(x + n, y);
        }

        if (flag) {
            if (node[p].lpos == node[p].rpos) {
                ans[node[p].lpos] = true;
            } else {
                solve(lp);
                solve(rp);
            }
        }

        // 撤销回溯
        while (dsu.stk.size() > top) {
            dsu.undo();
        }
    }
};

Merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int merge(int u, int v, int lpos, int rpos) {
    if (u == 0 || v == 0) {
        return u | v;
    }
    if (lpos == rpos) {
        sum[u] += sum[v];
        type[u] = lpos;
        return u;
    }
    int mid = (lpos + rpos) >> 1;
    ls[u] = merge(ls[u], ls[v], lpos, mid); // 可持久化要动态开点
    rs[u] = merge(rs[u], rs[v], mid + 1, rpos);
    push_up(u);
    return u;
}

Split

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// u -> v;
void spilt(int u, int& v, long long k, int lpos = 1, int rpos = n) {
    if (!v) {
        v = ++tot;
    }
    if (u == 0) {
        return;
    }
    if (lpos == rpos) {
        sum[v] = sum[u] - k;
        sum[u] = k;
        return;
    }
    long long s = sum[ls[u]];
    int mid = (lpos + rpos) >> 1;
    if (k <= s) {
        spilt(ls[u], ls[v], k, lpos, mid);
        swap(rs[u], rs[v]);
    } else { 
        spilt(rs[u], rs[v], k - s, mid + 1, rpos);
    }
    push_up(u);
    push_up(v);
}

Linear basis

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
template<int N>
struct linear_basis {
    long long cnt;
    long long basis[N];
    linear_basis() {
        for (int i = 0; i < N; i++) {
            basis[i] = 0;
        }
        cnt = 0;
    }

    bool insert(long long x) {
        for (int i = N - 1; ~i; i--) {
            if ((x >> i) & 1) {
                if (basis[i]) {
                    x ^= basis[i];
                }
                else {
                    basis[i] = x;
                    cnt++;
                    return true;
                }
            }
        }
        return false;
    }

    long long max_val(long long k = 0) {
        long long res = k;
        for (int i = N - 1; ~i; i--) {
            res = max(res, res ^ basis[i]);
        }
        return res;
    }

    long long size() const {
        return cnt;
    }

    void merge(const linear_basis<N>& other) {
        for (int i = 0; i < N; i++) {
            insert(other.basis[i]);
        }
    }

    void clear() {
        for (int i = 0; i < N; i++) {
            basis[i] = 0;
        }
        cnt = 0;
    }

    void orthogonalize() {//正交化
        for (int i = N - 1; ~i; i--) {
            for (int j = i - 1; ~j; j--) {
                if ((basis[i] >> j) & 1) {
                    basis[i] ^= basis[j];
                }
            }
        }
    }

    long long kth(long long k) {//第k小
        vector<long long> tep;
        for (int i = 0; i < N; i++) {
            if (basis[i]) {
                tep.push_back(basis[i]);
            }
        }

        long long res = 0;
        for (int i = 0; i < tep.size(); i++) {
            if ((k >> i) & 1) {
                res ^= tep[i];
            }
        }
        return res;
    }

    long long rk(long long x) {//查数排名
        long long l = 1;
        long long r = (1ll << size()) - 1;
        while (l <= r) {
            long long Mid = (l + r) >> 1;
            long long val = kth(Mid);
            if (val == x) {
                return Mid;
            }
            else if (val > x) {
                r = Mid - 1;
            }
            else {
                l = Mid + 1;
            }
        }
        return -1;
    }
};