BZOJ 1455 羅馬遊戲：左偏樹可並堆合併集合查詢最小值

BZOJ 1455 羅馬遊戲：左偏樹可並堆合併集合查詢最小值

題目大意

N (≤10⁶) 個元素，每個有權值。兩操作：
M x y：合併 x、y 所在集合
K x：刪除並輸出 x 所在集合的最小權值元素
輸出 0 表示集合為空或元素已刪除。

左偏樹（可並堆）

• 支持合併、插入、刪除最小值，均攤 O(log N)
• 結構：每節點維護左/右子、距離、權值、位置
• 合併遞歸：權值大的作右子遞歸合併，再交換左右保證左距 ≥ 右距，更新距離
• 刪最小：合併左右子樹

核心代碼

#include 
#include 
#include 
#define M 1001001
using namespace std;

struct Node {
    Node *l, *r; int dist, pos, val;
    Node(int p=0, int v=0x3f3f3f3f) : l(null), r(null), dist(-1), pos(p), val(v) {}
} *null = new Node(), *rt[M];

Node* merge(Node* a, Node* b) {
    if (a == null) return b;
    if (b == null) return a;
    if (a->val > b->val) swap(a, b); // 小根堆
    a->r = merge(a->r, b);
    if (a->l->dist < a->r->dist) swap(a->l, a->r);
    a->dist = a->r->dist + 1;
    return a;
}

int fa[M]; bool del[M];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    fa[x] = y;
    rt[y] = merge(rt[x], rt[y]);
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int v; scanf("%d", &v);
        rt[i] = new Node(i, v);
        fa[i] = i;
    }
    int m; scanf("%d", &m);
    char op[10];
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'M') {
            int x, y; scanf("%d%d", &x, &y);
            if (del[x] || del[y]) continue;
            unite(x, y);
        } else {
            int x; scanf("%d", &x);
            if (del[x]) { puts("0"); continue; }
            x = find(x);
            printf("%d\n", rt[x]->val);
            del[rt[x]->pos] = true;
            rt[x] = merge(rt[x]->l, rt[x]->r);
        }
    }
    return 0;
}

關鍵點

• 並查集維護集合屬屬，左偏樹維護集合內最小值
• 合併時同時合併並查集與堆
• 刪除標記 del[] 防止重複刪除
• N=10⁶ 需靜態節點池避免 new 慢，代碼簡化用 new

此題是「可並堆 + 並查集」的標準組合，左偏樹代碼極短且高效。