POJ 2828 插孔問題：線段樹離線處理逆序構造最終序列

題目大意

給定 n 個數，按順序插入序列。第 i 個數插入位置為 pos[i] (0-based，在當前序列中)。求最終序列。
示例：n=4，(pos, val) = (0,77), (1,51), (1,33), (2,69) → 最終 77 33 69 51。

核心洞察：逆序處理 + 線段樹維護空位

正序插入需移動後續元素，困難。逆序思考：最終序列長度固定為 n。最後插入的元素位置已定，倒數第二個插入時，它的位置在「剩餘空位」中確定……

算法流程

1. 構建線段樹，葉子節點代表最終序列的 n 個位置，初始值 1 (空位)
2. 內部節點維護區間 空位總數
3. 從 i = n 到 1 逆序處理：
   • 查找第 pos[i]+1 個空位 (1-based)
   • 將 val[i] 放入該位置
   • 更新線段樹：該位置空位數 -1
4. 最終線段樹葉子即為答案

線段樹操作

struct Node { int cnt; } tree[4*MAXN];

void build(int p, int l, int r) {
    tree[p].cnt = r - l + 1;
    if (l == r) return;
    int mid = (l+r)/2;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
}

// 找第 k 個空位 (k 1-based)，並佔用
int query(int p, int l, int r, int k) {
    tree[p].cnt--;
    if (l == r) return l;
    int mid = (l+r)/2;
    if (k <= tree[p*2].cnt) return query(p*2, l, mid, k);
    else return query(p*2+1, mid+1, r, k - tree[p*2].cnt);
}

完整代碼

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200010;
struct Node { int cnt; } tree[4*MAXN];
int pos[MAXN], val[MAXN], ans[MAXN];

void build(int p, int l, int r) {
    tree[p].cnt = r - l + 1;
    if (l == r) return;
    int mid = (l+r)/2;
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
}

int query(int p, int l, int r, int k) {
    tree[p].cnt--;
    if (l == r) return l;
    int mid = (l+r)/2;
    if (k <= tree[p*2].cnt) return query(p*2, l, mid, k);
    else return query(p*2+1, mid+1, r, k - tree[p*2].cnt);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            cin >> pos[i] >> val[i];
            ++pos[i]; // 0-based → 1-based (第 k 個空位)
        }
        build(1, 1, n);
        for (int i = n; i >= 1; --i) {
            int idx = query(1, 1, n, pos[i]);
            ans[idx] = val[i];
        }
        for (int i = 1; i <= n; ++i) {
            if (i > 1) cout << ' ';
            cout << ans[i];
        }
        cout << '\n';
    }
    return 0;
}

複雜度分析

• 構建樹：O(n)
• 每次查詢/更新：O(log n)
• 總時間：O(n log n)
• 空間：O(n)

關鍵技巧總結

1. 逆序處理：將「插入位置」轉化為「第 k 個空位查找」
2. 線段樹維護空位計數：支持 O(log n) 查找第 k 個空位
3. 離線算法：無需在線回答，可預讀所有操作逆序處理

相關題目

• SPOJ ORDERSET / GSS 系列
• 「第 k 個數」查找：線段樹、平衡樹、树状数组 + 二分
• JOI 2008 最終排名 (同類逆序插孔)

本題是線段樹離線處理動態序列的教科書級範例：逆序思維 + 空位計數 + 第 k 個查找，完美解決「動態插入查詢最終序列」問題。理解此模式，可舉一反三解決大批「動態序列構造」題目。