POJ 2828 Buy Tickets：線段樹解決插隊問題，逆序構建最終隊列

問題建模

N 人依次插隊。第 i 人（1-based）插在第 Pos_i 人之後（Pos_i=0 表示最前面）。已知每人值 Val_i。求最終隊列從前到後的值序列。N ≤ 200,000。

逆序思維 + 線段樹

正向插隊難維護，但 逆向 很容易：
最後一個人（i=N）的位置已確定：他前面有 Pos_N 個空位，即第 Pos_N+1 個空位。
倒數第二個人（i=N-1）同理，在他插入時，後面的人還沒來，所以他也佔據第 Pos_{N-1}+1 個空位。
以此類推，從 i=N 到 1，每人佔據當前剩餘空位中的第 Pos_i+1 個。

線段樹維護空位

• 葉子節點對應隊列位置 1..N，初始值 1（空）。
• 內部節點存區間空位總數 sum。
• 查找第 k 個空位：從根遞歸，若左子樹 sum ≥ k 往左，否則 k -= left.sum 往右。
• 佔據位置後將該葉子置 0，向上更新 sum。

完整 C++ 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
struct Node { int pos, val; } p[MAXN];
int sum[MAXN<<2];

void build(int o, int l, int r) {
    if (l == r) { sum[o] = 1; return; }
    int mid = (l+r)/2;
    build(o*2, l, mid); build(o*2+1, mid+1, r);
    sum[o] = sum[o*2] + sum[o*2+1];
}

int query(int o, int l, int r, int k) { // 找第 k 個空位
    if (l == r) { sum[o] = 0; return l; }
    int mid = (l+r)/2;
    int pos = (sum[o*2] >= k) ? query(o*2, l, mid, k)
                              : query(o*2+1, mid+1, r, k - sum[o*2]);
    sum[o] = sum[o*2] + sum[o*2+1];
    return pos;
}

int ans[MAXN];
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &p[i].pos, &p[i].val);
            p[i].pos++; // 0-based pos → 1-based 空位序號
        }
        build(1, 1, n);
        for (int i = n-1; i >= 0; i--) {
            int idx = query(1, 1, n, p[i].pos);
            ans[idx] = p[i].val;
        }
        for (int i = 1; i <= n; i++) {
            if (i > 1) putchar(' ');
            printf("%d", ans[i]);
        }
        putchar('\n');
    }
    return 0;
}

複雜度分析

• 建樹：\( O(N) \)
• N 次查找+更新：\( O(N \log N) \)
• 總時間：\( O(N \log N) \)，N=200,000 約 300 萬操作，極快。
• 空間：\( O(N) \)。

關鍵技巧總結

1. 逆序處理：將動態插入轉化為靜態選位。
2. 線段樹維護「第 k 個空位」：經典應用，類似「第 k 小數」但值域為 0/1。
3. 輸出格式：空格分隔，行末無多餘空格。

總結

POJ 2828 是線段樹「維護空位、查找第 k 個」的教科書級例題。逆序思維將 O(N²) 模擬降為 O(N log N)，代碼簡潔優雅。此模板廣泛適用於「動態插入/刪除、查找第 k 個可用位置」的問題。