POJ 2828 Buy Tickets：線段樹模擬插隊過程 (離線逆序構建)

問題描述

N 個人 (1~N) 依次到達。第 i 人插在當前隊列中第 Pos_i 個人後面 (Pos_i ∈ [0, i-1]，0 表示隊首)。每人有一個值 Val_i。求最終隊列從前到後的值序列。N≤200,000。

核心技巧：逆序處理 + 線段樹維護空位

正向模擬插隊需移動大量元素 O(N²)。逆向思維：

1. 最終隊列有 N 個位置，初始全空。
2. 從 i=N 遞減到 1：第 i 人最終位置是當前空位中第 Pos_i+1 個 (因他插在 Pos_i 後面，即佔據第 Pos_i+1 個空位)。
3. 用線段樹維護區間空位數，支持「查找第 k 個空位」和「標記位置佔用」。

線段樹節點信息

struct Node {
    int l, r;
    int sum; // 區間內空位數
} tree[4*MAXN];

關鍵操作

• Build：遞歸構建，葉子 sum=1 (初始全空)，內部節點 sum = left.sum + right.sum。
• Query/Update (找第 k 空位並佔用)：

  void update(int k, int val, int idx=1) { // k: 第k個空位, val: 人的值
      if (tree[idx].l == tree[idx].r) {
          tree[idx].sum = 0;
          ans[tree[idx].l] = val; // 記錄最終隊列值
          return;
      }
      if (k <= tree[idx*2].sum) update(k, val, idx*2);
      else update(k - tree[idx*2].sum, val, idx*2+1);
      tree[idx].sum = tree[idx*2].sum + tree[idx*2+1].sum;
  }

完整流程

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector pos(n+1), val(n+1);
        for (int i=1; i<=n; ++i) scanf("%d%d", &pos[i], &val[i]);
        build(1, n, 1); // 1~n 位置
        for (int i=n; i>=1; --i) {
            update(pos[i] + 1, val[i], 1); // 佔據第 pos[i]+1 個空位
        }
        for (int i=1; i<=n; ++i) {
            printf("%d%c", ans[i], i==n?'\n':' ');
        }
    }
    return 0;
}

複雜度分析

• 時間：O(N log N) — N 次線段樹查找/更新。
• 空間：O(N) — 線段樹 4N 節點。

關鍵點

• 離線逆序：將動態插入轉化為靜態佔位，避免數組移動。
• 線段樹找第 k 個：利用左子樹 sum 決定遞歸方向，經典用法。
• Pos_i 含義：插在 Pos_i 後面 → 佔據第 Pos_i+1 個空位。

總結

POJ 2828 是「線段樹找第 k 個空位」的經典應用。逆序離線思想將 O(N²) 插隊模擬優化為 O(N log N)，是處理「動態插入/刪除求最終順序」問題的標準範式 (如順序表重構、排名系統)。