POJ 1442：雙堆維護有序序列與迭代器

問題描述

支援兩種操作：

• ADD(x)：將 x 插入有序序列。
• GET()：返回全局迭代器指向的值，隨後迭代器 ++。

初始序列 S[1..m] 給定，操作序列 op[1..n] 中每個數字表示 GET 前需 ADD 多少個元素。

雙堆策略

維護兩個堆：

• 大頂堆 q1：存放已排序序列的前半部 S[1..k]，堆頂為第 k 小元素。
• 小頂堆 q2：存放後半部 S[k+1..n]，堆頂為第 k+1 小元素。

不變量：q1.size() == k，且 q1.top() <= q2.top()。GET() 直接取 q1.top()，然後將其移至 q2，k++。

添加元素邏輯

1. 新元素先入 q1。
2. 若 q1.top() > q2.top()，交換兩堆頂元素，恢復有序性。
3. 若 q1.size() > k，將 q1.top() 移至 q2。

核心代碼

#include <queue>
#include <cstdio>
using namespace std;

struct MinCmp { bool operator()(int a, int b) { return a > b; } }; // 小頂堆
struct MaxCmp { bool operator()(int a, int b) { return a < b; } }; // 大頂堆

void Test() {
    priority_queue<int, vector<int>, MinCmp> q1; // 大頂堆（存前半）
    priority_queue<int, vector<int>, MaxCmp> q2; // 小頂堆（存後半）

    for (int i = 0; i < m; ++i) scanf("%d", &sequence[i]);

    int k = 0;
    for (int i = 0; i < n; ++i) {
        int op; scanf("%d", &op);
        while (k < op) {
            q1.push(sequence[k]);
            if (!q2.empty() && q1.top() < q2.top()) {
                int t1 = q1.top(); q1.pop();
                int t2 = q2.top(); q2.pop();
                q1.push(t2); q2.push(t1);
            }
            ++k;
        }
        printf("%d ", q1.top());
        q2.push(q1.top());
        q1.pop();
    }
}

複雜度分析

• 每個元素最多進出堆常數次：O((m+n) log m)。
• 空間 O(m)。

關鍵洞見

將「迭代器位置」轉化為「大小堆分界線」，利用堆的 top() 即時獲取第 k 小元素，避免了鏈表模擬的 O(n²) 瓶頸。此技巧常用於「動態中位數」「滑動窗口中位數」等問題。