POJ 2828：Buy Tickets——線段樹維護隊列插入位置

題目描述

N 人（N ≤ 200,000）依次插隊。第 i 人給定 Posᵢ ∈ [0, i-1] 和值 Valᵢ，表示插在當前隊列第 Posᵢ 人後面（0 為售票口）。求最終隊列順序。

逆序插入 + 線段樹

最後插入的人位置固定。從最後一人倒推：每人需在當前空位中找第 Posᵢ+1 個位置放入。線段樹維護區間空位數，查找第 k 個空位 O(log N)。

線段樹節點

st[p]：區間內剩餘空位數。葉子初始為 1（空）。

C++ 實現

#include <cstdio>
#define MAX 200005
int st[MAX<<2], val[MAX], pos[MAX];

void build(int l, int r, int p) {
    if (l == r) { st[p] = 1; return; }
    int mid = (l+r)>>1;
    build(l, mid, p<<1);
    build(mid+1, r, p<<1|1);
    st[p] = st[p<<1] + st[p<<1|1];
}

void insert(int v, int k, int l, int r, int p) { // 在第 k 個空位放 v
    if (l == r) { val[l] = v; st[p] = 0; return; }
    int mid = (l+r)>>1;
    if (k <= st[p<<1]) insert(v, k, l, mid, p<<1);
    else insert(v, k - st[p<<1], mid+1, r, p<<1|1);
    st[p] = st[p<<1] + st[p<<1|1];
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        build(1, n, 1);
        for (int i = 0; i < n; ++i) scanf("%d%d", &pos[i], &val[i]);
        for (int i = n-1; i >= 0; --i) insert(val[i], pos[i]+1, 1, n, 1);
        for (int i = 1; i <= n; ++i) {
            printf("%d", val[i]);
            if (i < n) putchar(' ');
        }
        puts("");
    }
    return 0;
}

複雜度

• 構建：O(N)
• N 次插入：O(N log N)
• 總時間：~1.5s（優化 IO 可更快）