POJ 2828 Buy Tickets：線段樹逆序插入還原隊列順序

POJ 2828 Buy Tickets：線段樹逆序插入還原隊列順序

題目背景

N (≤200,000) 人依次加入隊列。第 i 人插入到第 Pos_i 人之後（0 表示最前面）。已知所有人的插入位置 Pos_i 與數值 Val_i，求最終隊列從前到後的數值序列。

關鍵洞察：逆向構建

正向插入需移動大量元素，O(N²) 不可行。觀察可知：

• 最後一人 (i=N) 的位置確定無歧義
• 倒序處理：當處理第 i 人時，後面 i+1..N 人已安排妥當，隊列中有 N-i 個空位
• 第 i 人要站在第 Pos_i+1 個空位（因為 Pos_i 人已在隊列中）

線段樹維護空位

線段樹節點存儲區間內剩餘空位數。查詢第 k 個空位並佔用，單點更新，O(log N)。

核心代碼

struct Node { int l, r, num; } seg[800000];
int ans[200005], pos[200005], val[200005];

void build(int rt, int l, int r) {
    seg[rt].l = l; seg[rt].r = r; seg[rt].num = r - l + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(rt<<1, l, mid);
    build(rt<<1|1, mid+1, r);
}

void query(int rt, int k, int v) { // 找第 k 個空位放入值 v
    --seg[rt].num;
    if (seg[rt].l == seg[rt].r) {
        ans[seg[rt].l] = v;
        return;
    }
    if (seg[rt<<1].num >= k) query(rt<<1, k, v);
    else query(rt<<1|1, k - seg[rt<<1].num, v);
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        for (int i = 1; i <= n; ++i) scanf("%d%d", &pos[i], &val[i]);
        build(1, 1, n);
        for (int i = n; i >= 1; --i)
            query(1, pos[i] + 1, val[i]); // 逆序插入
        for (int i = 1; i < n; ++i) printf("%d ", ans[i]);
        printf("%d\n", ans[n]);
    }
    return 0;
}

樣例演示

輸入：
4
0 77
1 51
1 33
2 69

輸出：
77 33 69 51

複雜度

• 時間：O(N log N)
• 空間：O(N)

此題展示了「逆向思維 + 線段樹維護順序統計」的經典組合，是處理動態插入順序問題的標準解法。