BZOJ 1455 羅馬遊戲：可並堆（Leftist Heap）解題詳解

題目大意

給定 n 個人的權值，需支援兩種操作：將兩隊人合併為一堆，或刪除某堆中權值最小的人。每次刪除操作需輸出被刪除者的權值。

解題思路

此題核心為可並堆（Mergeable Heap）資料結構。作者選用最簡單的隨機堆（Randomized Heap）實現。隨機堆透過隨機決定合併時的左右子樹，期望時間複雜度為 O(log n)，且程式碼極為精簡。

並查集（Union-Find）用於維護每個人的所屬堆，配合 killed 陣列標記已刪除的節點，確保操作正確性。

關鍵程式碼解析

#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX 1000010
using namespace std;

struct Heap {
    Heap *son[2];
    int val;
    Heap(int _):val(_) { son[0] = son[1] = NULL; }
    Heap() {}
} *heap[MAX], mempool[MAX], *C = mempool + 1;

Heap *Merge(Heap *x, Heap *y) {
    if (x == NULL) return y;
    if (y == NULL) return x;
    if (x->val > y->val) swap(x, y); // 保持小根堆性質
    bool k = rand() & 1;               // 隨機選擇左右子樹
    x->son[k] = Merge(x->son[k], y);
    return x;
}

int points, asks;
int src[MAX];
bool killed[MAX];
char s[10];
int father[MAX];

int Find(int x) {
    if (father[x] == x) return x;
    return father[x] = Find(father[x]);
}

int main() {
    srand(19970806);
    cin >> points;
    for (int i = 1; i <= points; ++i) father[i] = i;
    for (int x, i = 1; i <= points; ++i) {
        scanf("%d", &x);
        heap[i] = new (C++) Heap(x);
    }
    cin >> asks;
    for (int x, y, i = 1; i <= asks; ++i) {
        scanf("%s", s);
        if (s[0] == 'M') { // 合併操作
            scanf("%d%d", &x, &y);
            if (killed[x] || killed[y]) continue;
            int fx = Find(x), fy = Find(y);
            if (fx == fy) continue;
            father[fy] = fx;
            heap[fx] = Merge(heap[fx], heap[fy]);
        } else { // 刪除最小值
            scanf("%d", &x);
            if (killed[x]) { puts("0"); continue; }
            int fx = Find(x);
            printf("%d\n", heap[fx]->val);
            killed[heap[fx] - mempool] = true;
            heap[fx] = Merge(heap[fx]->son[0], heap[fx]->son[1]);
        }
    }
    return 0;
}

複雜度分析

• 合併操作：期望 O(log n)
• 刪除最小值：期望 O(log n)
• 空間複雜度：O(n)

隨機堆因實作簡單、常數小，在競程中常作為左式堆或斜堆的替代方案。