POJ 1442：Treap（樹堆）與雙優先隊列兩種解法維護動態中位數

問題描述

給定序列 A[1..n] 與查詢位置 B[1..m]（遞增），每次將 A[i] 插入數據結構，當 i 等於某 B[k] 時輸出當前第 k 小的數。n,m ≤ 30000。

解法一：Treap（隨機化平衡二叉搜索樹）

維護 size（子樹節點數）與 counts（重複值計數）。插入時按 BST 性質遞歸，旋轉維護堆性質（r[child] < r[parent]）。查詢第 k 小：遞歸比較左子樹大小與 counts 決定走向。均攤 O(log n)。

void insert(int &rt, int v) {
    if(!rt) { newnode(rt,v); return; }
    if(val[rt]==v) counts[rt]++;
    else {
        int d = (val[rt] < v);
        insert(ch[rt][d], v);
        if(r[ch[rt][d]] < r[rt]) rotate(rt, d^1);
    }
    pushup(rt);
}
int select(int rt, int k) {
    if(size[ch[rt][0]] >= k) return select(ch[rt][0], k);
    if(size[ch[rt][0]] + counts[rt] >= k) return val[rt];
    return select(ch[rt][1], k - size[ch[rt][0]] - counts[rt]);
}

解法二：雙優先隊列（大根堆 + 小根堆）

維護兩堆：q1（大根堆）存較小一半，q2（小根堆）存較大一半，保證 q2.size() == k 時堆頂即第 k 小。插入新元素時先比較 q1.top() 決定放入哪堆，再平衡堆大小。O(log n) 且常數極小。

priority_queue<int, vector<int>, less<int>> q1; // 大根堆
priority_queue<int, vector<int>, greater<int>> q2; // 小根堆

for(int i=1;i<=n;++i) {
    if(!q1.empty()) {
        if(a[i] < q1.top()) q2.push(a[i]);
        else { q2.push(q1.top()); q1.pop(); q1.push(a[i]); }
    } else q2.push(a[i]);
    while(b[k]==i) {
        // 平衡 q2 大小至 k
        while(q2.size() > k) { q1.push(q2.top()); q2.pop(); }
        while(q2.size() < k) { q2.push(q1.top()); q1.pop(); }
        printf("%d\n", q2.top()); k++;
    }
}

複雜度對比

兩者均為 O((n+m) log n)。Treap 代碼較長但功能強大（支持刪除、區間操作）；雙堆代碼極短、常數優、專治動態中位數/第 k 小。視題目需求選擇。