ZOJ 2334 Monkey King 解題報告：左偏樹與並查集的經典結合

問題背景

ZOJ 2334 Monkey King 是左偏樹的模板題，核心需維護集合關係，並查集極適合處理動態合併與查詢；同時需記錄每個節點所屬左偏樹的編號，以便快速存取堆頂元素。

核心資料結構

• 左偏樹：支援合併、插入、刪除堆頂、查詢堆頂等操作，均攤複雜度 O(log n)。
• 並查集：維護猴子群體的集合關係，支援路徑壓縮的 find 操作。
• id[] 陣列：記錄每個集合代表元對應的左偏樹根節點編號。

演算法流程

1. 初始化：每隻猴子自成一集合，建立單節點左偏樹，id[i] = i。
2. 處理每次操作 (a, b)：
   • 若 find(a) == find(b)，輸出 -1。
   • 否則分別取出兩集合左偏樹的堆頂（戰力最強猴子），戰力減半後重新插入各自左偏樹。
   • 合併兩集合的並查集與左偏樹，輸出新堆頂戰力。

關鍵程式碼片段

// 左偏樹合併
int Merge(int x, int y) {
    if (!x) return y;
    if (!y) return x;
    if (v[x] < v[y]) swap(x, y);          // 大根堆
    r[x] = Merge(r[x], y);
    if (d[l[x]] < d[r[x]]) swap(l[x], r[x]); // 維護左偏性質
    d[x] = d[r[x]] + 1;
    return x;
}

// 並查集查找
int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); }

// 主流程
while (m--) {
    scanf("%d%d", &a, &b);
    int x = _find(a), y = _find(b);
    if (x == y) { puts("-1"); continue; }
    int u = top(id[x]); id[x] = pop(id[x]); id[x] = Insert(id[x], u/2);
    u = top(id[y]); id[y] = pop(id[y]); id[y] = Insert(id[y], u/2);
    p[x] = y;
    id[y] = Merge(id[x], id[y]);
    printf("%d\n", top(id[y]));
}

複雜度分析

每次操作涉及常數次左偏樹合併與並查集查找，時間複雜度 O(log n)，空間複雜度 O(n)，完全滿足題目限制。

總結

本題完美展示左偏樹與並查集結合處理動態集合合併與優先隊列操作的威力，是掌握進階資料結構的優質練習題。