锰锌求助简单小问题

Netheris @ 2024-12-19 20:33:14

by wonaiWzhuoS @ 2024-12-19 20:34:45

注：指代 FHQ-Treap 的值域有相交的合并。

by wonaiWzhuoS @ 2024-12-19 20:36:49

struct Treap {
    struct Info {
        int ls, rs, key, sz, val, mn;
    } t[200001];
  // 一些东西……
  inline void push_up(int i) {
// 更新 sz 和 mn（最小值）
  }
    inline void split(int u, int x, int &l, int &r) { // 正常的平衡树分裂
        if (!u) return l = r = 0, void();
        if (t[u].vala <= x) {
            l = u;
            split(t[u].rs, x, t[u].rs, r);
        } else {
            r = u;
            split(t[u].ls, x, l, t[u].ls);
        }
        push_up(u);
    }
    inline int merge(int x, int y) { // 正常的平衡树合并
        if (!x || !y) return x | y;
        if (t[x].key < t[y].key) {
            t[x].rs = merge(t[x].rs, y);
            push_up(x);
            return x;
        } else {
            t[y].ls = merge(x, t[y].ls);
            push_up(y);
            return y;
        }
    }
    inline int Merge(int les, int gre) { // 势能分析平衡树合并（问的是这个能不能卡），用于值域有相交
        int res = 0;
        while (les && gre) {
            if (t[les].mn > t[gre].mn) swap(les, gre);
            int tmp;
            split(les, t[gre].mn, tmp, les);
            res = merge(res, tmp);
        }
        if (gre) res = merge(res, gre);
        if (les) res = merge(res, les);
        return res;
    }
} t;

by Netheris @ 2024-12-19 21:03:44

@Miss_SGT

@small_john

救救我救救我救救我救救我

by wonaiWzhuoS @ 2024-12-19 21:04:07

@Joker_Fish @radio

by wonaiWzhuoS @ 2024-12-19 21:15:11

救救我救救我救救我救救我你们一定会的你们一定会的你们一定会的你们一定会的

by _determination_ @ 2024-12-20 14:09:41

@sigma_zjx?我不会平衡树合并啊

by Miss_SGT @ 2024-12-20 14:32:11

不会哦

by Miss_SGT @ 2024-12-20 14:32:33

让我们启发式

by Miss_SGT @ 2024-12-20 14:59:35

使用线段树

by wonaiWzhuoS @ 2024-12-20 17:25:56

@Miss_SGT 6