Skip to content
TechMind

数据结构

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
struct DSU
{
    int n;
    vector<int> fa, size;
    DSU(int a = 0) { init(a); }
    void init(int a)
    {
        n = a;
        fa.assign(n + 1, 0);
        size.assign(n + 1, 1);
        for (int i = 1; i <= n; i++)
            fa[i] = i;
    }

    int find(int x)
    {
        if (x != fa[x])
            fa[x] = find(fa[x]);
        return fa[x];
    }

    bool merge(int x, int y)
    {
        x = find(x), y = find(y);
        if (x == y)
            return 0;
        if (size[x] < size[y])
            swap(x, y);
        size[x] += size[y];
        fa[y] = x;
        return 1;
    }

    bool same(int a, int b) { return find(a) == find(b); }

    int sz(int a) { return size[find(a)]; }
};

BIT🧀

单点1D🧀

 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
struct BIT
{
    int n, lg;
    vector<int> w;

    BIT(int _n)
    {
        n = _n;
        w.resize(n + 1);
        lg = __lg(n);
    }

    void add(int x, int k)
    {
        for (; x <= n; x += x & -x)
            w[x] += k;
    }

    int ask(int x)
    {
        if (x == 0)
            return 0;
        int ans = 0;
        for (; x; x -= x & -x)
            ans += w[x];
        return ans;
    }

    int ask(int x, int y)
    {
        if (x == 1)
            return ask(y);
        return ask(y) - ask(x - 1);
    }

    int kth(int k)
    {
        int pos = 0;
        for (int i = 1 << lg; i; i >>= 1)
        {
            int nxt = pos + i;
            if (nxt <= n && w[nxt] < k)
            {
                k -= w[nxt];
                pos = nxt;
            }
        }
        return pos + 1;
    }
};

区间2D🧀

 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
template <class T>
struct BIT_2D
{
    int n, m;
    vector<vector<T>> b1, b2, b3, b4;

    BIT_2D(int n, int m) : n(n), m(m)
    {
        b1.resize(n + 1, vector<T>(m + 1));
        b2.resize(n + 1, vector<T>(m + 1));
        b3.resize(n + 1, vector<T>(m + 1));
        b4.resize(n + 1, vector<T>(m + 1));
    }

    void matrixAdd(int x, int y, int X, int Y, T k)
    { // 区块修改：二维差分
        X++, Y++;
        auto add = [&](int x, int y, T k)
        {
            for (int i = x; i <= n; i += i & -i)
                for (int j = y; j <= m; j += j & -j)
                {
                    b1[i][j] += k;
                    b2[i][j] += k * (x - 1);
                    b3[i][j] += k * (y - 1);
                    b4[i][j] += k * (x - 1) * (y - 1);
                }
        };
        add(x, y, k);
        add(X, y, -k);
        add(x, Y, -k);
        add(X, Y, k);
    }

    T matrixSum(int x, int y, int X, int Y)
    { // 区块查询：二维前缀和
        x--, y--;
        auto ask = [&](int x, int y)
        {
            T ans = T();
            for (int i = x; i; i -= i & -i)
                for (int j = y; j; j -= j & -j)
                {
                    ans += x * y * b1[i][j];
                    ans -= y * b2[i][j];
                    ans -= x * b3[i][j];
                    ans += b4[i][j];
                }
            return ans;
        };
        return ask(X, Y) - ask(x, Y) - ask(X, y) + ask(x, y);
    }
};

Seg🧀

lazy🧀

  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
template <typename T>
struct seg
{
    struct node
    {
        int l, r;
        T w, lazy;
        node operator+(const node &other) const
        {
            node res;
            res.l = l;
            res.r = other.r;
            res.w = w + other.w;
            res.lazy = 0;
            return res; // lazy不参与合并，重置为0
        }
    };
    vector<T> w;
    vector<node> t;

    inline int ls(int k) { return k << 1; }
    inline int rs(int k) { return k << 1 | 1; }
    inline void pushup(int k) { t[k] = t[ls(k)] + t[rs(k)]; }

    seg(int n)
    {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }

    seg(vector<T> in)
    {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++)
            w[i] = in[i];
        t.resize((n << 2) + 1);
        build(1, n);
    }

    inline void update(int k, T lazy)
    {
        t[k].w += (t[k].r - t[k].l + 1) * lazy;
        t[k].lazy += lazy;
    }

    inline void pushdown(int k)
    {
        if (t[k].lazy == 0)
            return;
        update(ls(k), t[k].lazy);
        update(rs(k), t[k].lazy);
        t[k].lazy = 0;
    }

    void build(int l, int r, int k = 1)
    {
        if (l == r)
        {
            t[k] = {l, r, w[l], 0};
            return;
        }
        t[k] = {l, r};
        int mid = l + r >> 1;
        build(l, mid, ls(k));
        build(mid + 1, r, rs(k));
        pushup(k);
    }

    void modify(int l, int r, T v, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
        {
            update(k, v);
            return;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (l <= mid)
            modify(l, r, v, ls(k));
        if (r > mid)
            modify(l, r, v, rs(k));
        pushup(k);
    }

    node queryNode(int l, int r, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
            return t[k];
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (r <= mid)
            return queryNode(l, r, ls(k));
        if (l > mid)
            return queryNode(l, r, rs(k));
        return queryNode(l, r, ls(k)) + queryNode(l, r, rs(k));
    }

    T query(int l, int r, int k = 1)
    {
        return queryNode(l, r, k).w;
    }
};

unlazified🧀

 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
template <typename T>
struct seg
{
    struct node
    {
        int l, r;
        T w;
        node operator+(const node &other) const
        {
            node res;
            res.l = l;
            res.r = other.r;
            res.w = w + other.w;
            return res;
        }
    };

    vector<T> w;
    vector<node> t;

    inline int ls(int k) { return k << 1; }
    inline int rs(int k) { return k << 1 | 1; }
    inline void pushup(int k) { t[k] = t[ls(k)] + t[rs(k)]; }

    seg(int n)
    {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }

    seg(vector<T> in)
    {
        int n = in.size() - 1;
        w.resize(n + 1);
        for (int i = 1; i <= n; i++)
            w[i] = in[i];
        t.resize((n << 2) + 1);
        build(1, n);
    }

    inline void update(int k, T v)
    {
        t[k].w += v;
    }

    void build(int l, int r, int k = 1)
    {
        if (l == r)
        {
            t[k] = {l, r, w[l]};
            return;
        }
        t[k] = {l, r};
        int mid = l + r >> 1;
        build(l, mid, ls(k));
        build(mid + 1, r, rs(k));
        pushup(k);
    }

    void modify(int pos, T v, int k = 1)
    {
        if (t[k].l == t[k].r)
        {
            update(k, v);
            return;
        }
        int mid = (t[k].l + t[k].r) >> 1;
        if (pos <= mid)
            modify(pos, v, ls(k));
        else
            modify(pos, v, rs(k));
        pushup(k);
    }

    node queryNode(int l, int r, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
            return t[k];
        int mid = (t[k].l + t[k].r) >> 1;
        if (r <= mid)
            return queryNode(l, r, ls(k));
        if (l > mid)
            return queryNode(l, r, rs(k));
        return queryNode(l, r, ls(k)) + queryNode(l, r, rs(k));
    }

    T query(int l, int r, int k = 1) { return queryNode(l, r, k).w; }
};

struct lazy🧀

  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
template <typename T>
struct seg
{
    struct node
    {
        int l, r;
        T w;
        struct lazytag
        {
            T mul, add; // x -> x * mul + add
            lazytag(T _mul = 1, T _add = 0) : mul(_mul), add(_add) {}
            lazytag operator+(const lazytag &other) const { return lazytag(mul * other.mul, add * other.mul + other.add); }
        } lazy;

        node operator+(const node &other) const { return {l, other.r, w + other.w, lazytag()}; }
    };

    vector<T> w;
    vector<node> t;

    inline int ls(int k) { return k << 1; }
    inline int rs(int k) { return k << 1 | 1; }
    inline void pushup(int k) { t[k] = t[ls(k)] + t[rs(k)]; }

    seg(int n)
    {
        w.resize(n + 1);
        t.resize((n << 2) + 1);
        build(1, n);
    }

    seg(const vector<T> &in)
    {
        int n = in.size() - 1;
        w = in;
        t.resize((n << 2) + 1);
        build(1, n);
    }

    inline void update(int k, const typename node::lazytag &lz)
    {
        t[k].w = t[k].w * lz.mul + (t[k].r - t[k].l + 1) * lz.add;
        t[k].lazy = t[k].lazy + lz;
    }

    inline void pushdown(int k)
    {
        if (t[k].lazy.mul == 1 && t[k].lazy.add == 0)
            return;
        update(ls(k), t[k].lazy);
        update(rs(k), t[k].lazy);
        t[k].lazy = typename node::lazytag();
    }

    void build(int l, int r, int k = 1)
    {
        if (l == r)
        {
            t[k] = {l, r, w[l], typename node::lazytag()};
            return;
        }
        int mid = (l + r) >> 1;
        t[k] = {l, r, 0, typename node::lazytag()};
        build(l, mid, ls(k));
        build(mid + 1, r, rs(k));
        pushup(k);
    }

    void modify(int l, int r, const typename node::lazytag &lz, int k = 1)
    {
        if (l <= t[k].l && t[k].r <= r)
        {
            update(k, lz);
            return;
        }
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (l <= mid)
            modify(l, r, lz, ls(k));
        if (r > mid)
            modify(l, r, lz, rs(k));
        pushup(k);
    }

    node queryNode(int l, int r, int k = 1)
    {
        if (l <= t[k].l && r >= t[k].r)
            return t[k];
        pushdown(k);
        int mid = (t[k].l + t[k].r) >> 1;
        if (r <= mid)
            return queryNode(l, r, ls(k));
        if (l > mid)
            return queryNode(l, r, rs(k));
        return queryNode(l, r, ls(k)) + queryNode(l, r, rs(k));
    }

    T query(int l, int r, int k = 1)
    {
        return queryNode(l, r, k).w;
    }
};

using lz = seg<int>::node::lazytag; // 套别的数据类型时需要修改

01trie🧀

 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
struct trie
{
    struct node
    {
        aii cnt, pts;
        node()
        {
            cnt[0] = cnt[1] = 0;
            pts[0] = pts[1] = 0;
        }
    };
    vec<node> tr;
    int cur;
    trie()
    {
        tr.resize(2);
        cur = 1;
    }

    void insert(int x)
    {
        int pt = 1;
        for (int j = 30; j >= 0; j--)
        {
            int bit = (x >> j) & 1;
            if (!tr[pt].pts[bit])
            {
                cur++;
                if (cur >= tr.size())
                    tr.resize(cur + 1);
                tr[pt].pts[bit] = cur;
            }
            tr[pt].cnt[bit]++;
            pt = tr[pt].pts[bit];
        }
    }

    int query(int x, int k)
    {
        int pt = 1, ans = 0;
        for (int j = 30; j >= 0; j--)
        {
            int bit = (x >> j) & 1;
            if (tr[pt].cnt[bit] < k)
            {
                k -= tr[pt].cnt[bit];
                bit ^= 1;
                ans |= (1 << j);
            }
            pt = tr[pt].pts[bit];
        }
        return ans;
    }
};

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
struct ST
{
    int n, k;
    vector<int> in;
    vector<vector<int>> mx;

    ST(vector<int> IN)
    {
        n = IN.size(), k = __lg(n), in = IN;
        mx.resize(k + 1, vector<int>(n));
        for (int i = 0; i < n; i++)
            mx[0][i] = in[i];
        for (int i = 0, t = 1; i < k; i++, t <<= 1)
        {
            const int T = n - (t << 1);
            for (int j = 0; j <= T; j++)
                mx[i + 1][j] = max(mx[i][j], mx[i][j + t]);
        }
    }

    int ask(int l, int r)
    {
        int k = __lg(r - l + 1);
        return max(mx[k][l], mx[k][r - (1 << k) + 1]);
    }
};