「v4」0x40 数据结构

    「v4」0x40 数据结构

    同步于 2026-11-11,花费 14,451,581 tok。

    0x41 数据结构 序列结构

    ST 表

    0x41 ST 表.cpp:

    // ST 表
    template <class T, auto op>
    struct SparseTable {
        int t;
        std::vector<std::vector<T>> f;
    
        SparseTable() {}
        SparseTable(int n, const std::vector<T> &a) {
            init(n, a);
        }
    
        void init(int n, const std::vector<T> &a) {
            t = std::__lg(n);
            f.assign(t + 1, std::vector<T>(n + 1));
            for (int i = 1; i <= n; i ++) {
                f[0][i] = a[i];
            }
            for (int j = 1; j <= t; j ++) {
                for (int i = 1; i <= n - (1 << j) + 1; i ++) {
                    f[j][i] = op(f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
                }
            }
        }
    
        T ask(int l, int r) {
            int k = std::__lg(r - l + 1);
            return op(f[k][l], f[k][r - (1 << k) + 1]);
        }
    };

    并查集

    0x41 可撤销并查集.cpp:

    // 可撤销并查集
    struct DSU {
        std::vector<int> sze;
        std::vector<int> fa;
        std::vector<std::pair<int, int>> his;
    
        DSU() {}
        DSU(int n) {
            init(n);
        }
    
        void init(int n) {
            sze.assign(n + 1, 1);
            fa.resize(n + 1);
            std::iota(fa.begin(), fa.end(), 0);
            his.clear();
        }
    
        int get(int x) {
            return fa[x] == x ? x : get(fa[x]); // 按秩合并不能路径压缩
        }
    
        bool merge(int x, int y) {
            int p = get(x), q = get(y);
            if (p == q) {
                return 0;
            }
            if (sze[p] > sze[q]) {
                std::swap(p, q);
            }
            his.push_back({p, q});
            sze[q] += sze[p], fa[p] = q;
            return 1;
        }
    
        int time() {
            return his.size();
        }
        void revert(int tim) {
            while (his.size() > tim) {
                auto [p, q] = his.back(); his.pop_back();
                sze[q] -= sze[p], fa[p] = p;
            }
        }
    };

    线段树

    扫描线

    势能线段树

    区间开平方:一个整数 xx 开平方 O(log⁡log⁡V)\mathcal{O}(\log \log V) 次之后就会变成 11。若区间 max=1\mathrm{max} = 1 则 return。

    区间取模:一个整数 xx (x≥px \ge p) 对 pp 取模,xx 至少变小一半。若区间 max<p\mathrm{max} < p 则 return。

    区间除法:整除 pp 之后,由于 ⌊max⁡p⌋−⌊min⁡p⌋≤⌈max⁡−min⁡p⌉\lfloor \frac{\max}{p} \rfloor - \lfloor \frac{\min}{p} \rfloor \leq \lceil \frac{\max - \min}{p} \rceil,区间最大值与最小值的差,多数情况下会减半。

    • 若区间 max−min=0\mathrm{max} - \mathrm{min} = 0,则区间加之后 return。
    • 若区间 max−min=1\mathrm{max} - \mathrm{min} = 1 且 ⌊max⁡p⌋≠⌊min⁡p⌋\lfloor \frac{\mathrm{\max}}{p} \rfloor \neq \lfloor \frac{\mathrm{\min}}{p} \rfloor,则区间加之后 return。

    区间按位与:一个二进制数 xx 与 vv 进行按位与,至多进行 log⁡V\log V 次有效操作。若区间(在二进制下)bitor⊆v\mathrm{bitor} \subseteq v 则 return。

    区间取最值(吉老师线段树):以区间取最小值为例:

    • 在线段树上的每一个节点 pp 需要维护:
      • mx:区间最大值。
      • cnt:区间最大值个数。
      • md:区间严格次大值。
    • 在区间修改时,若遇到一个“被询问区间完全覆盖的节点”时:
      • 若 x≥mxx \geq \mathrm{mx},则 return。
      • 若 x≤mdx \leq \mathrm{md},则暴力递归左右儿子修改。
      • 若 md<x<mx\mathrm{md} < x < \mathrm{mx},则有 cnt\mathrm{cnt} 个 mx\mathrm{mx} 被修改成 xx,打标记后 return。
    • 时间复杂度 O(nlog⁡2n)\mathcal{O}(n \log^2 n)。

    0x41 吉老师线段树.cpp:

    struct Info {
        int mx, md;
        int cnt;
        Info() {}
        Info(int mx, int md, int cnt) : mx(mx), md(md), cnt(cnt) {}
    
        friend Info operator + (Info l, Info r) {
            if (l.mx == r.mx) {
                return Info(l.mx, std::max(l.md, r.md), l.cnt + r.cnt);
            } else if (l.mx > r.mx) {
                return Info(l.mx, std::max(l.md, r.mx), l.cnt);
            } else {
                return Info(r.mx, std::max(l.mx, r.md), r.cnt);
            }
        }
    };
    
    // 吉老师线段树
    namespace SGT {
        struct node {
            int len;
            i64 sum;
            Info info;
    
            int add; // 加法标记(初始值等于 0)
            int tag; // 区间取 min 标记(初始值等于 +inf,需要根据数据范围修改)
            void mk_add(int x) {
                sum += 1ll * x * len;
                info.mx += x;
                if (info.md != -inf) info.md += x;
                add += x;
                if (tag < inf) tag += x;
            }
            void mk_tag(int x) {
                if (info.mx <= x) return;
                sum -= 1ll * (info.mx - x) * info.cnt;
                info.mx = x;
                tag = x;
            }
        } t[N * 4];
    
        void upd(int p) {
            t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
            t[p].info = t[p * 2].info + t[p * 2 + 1].info;
        }
    
        void spread(int p) {
            if (t[p].add) {
                t[p * 2].mk_add(t[p].add), t[p * 2 + 1].mk_add(t[p].add);
                t[p].add = 0;
            }
            if (t[p].tag < inf) {
                t[p * 2].mk_tag(t[p].tag), t[p * 2 + 1].mk_tag(t[p].tag);
                t[p].tag = inf;
            }
        }
    
        void build(int p, int l, int r) {
            t[p].add = 0, t[p].tag = inf, t[p].len = r - l + 1;
            if (l == r) {
                t[p].sum = a[l], t[p].info = Info(a[l], -inf, 1);
                return;
            }
            int mid = (l + r) >> 1;
            build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
            upd(p);
        }
    
        void change_add(int p, int l, int r, int s, int e, int x) {
            if (s <= l && r <= e) {
                t[p].mk_add(x);
                return;
            }
            spread(p);
            int mid = (l + r) >> 1;
            if (s <= mid) {
                change_add(p * 2, l, mid, s, e, x);
            }
            if (mid < e) {
                change_add(p * 2 + 1, mid + 1, r, s, e, x);
            }
            upd(p);
        }
    
        void change_min(int p, int l, int r, int s, int e, int x) {
            if (s <= l && r <= e && t[p].info.md < x) {
                t[p].mk_tag(x);
                return;
            }
            spread(p);
            int mid = (l + r) >> 1;
            if (s <= mid) {
                change_min(p * 2, l, mid, s, e, x);
            }
            if (mid < e) {
                change_min(p * 2 + 1, mid + 1, r, s, e, x);
            }
            upd(p);
        }
    }

    笛卡尔树

    区间笛卡尔树

    0x42 数据结构 树上结构