POJ 2828 線段樹單點更新：倒序插入求排列

題目大意

有 n 個人，每人有一對 (p_i, v_i)。從空序列開始，依序將第 i 個人插入到當前序列的第 p_i 個空位（1-based），其值為 v_i。最終輸出完整序列。

核心觀察

正向插入難以維護「空位」資訊，但倒序插入可轉化為：最終序列長度為 n，最後一個被插入的人（即輸入的第 n 人）會佔據第 p_n 個位置。倒推回去，每次在剩餘空位中選擇第 p_i 個位置放入 v_i。

線段樹設計

• 每個節點維護該區間空位數量 sum。
• 建樹時所有葉子初始化為 1（皆為空位）。
• update(pos, val)：在區間中找到第 pos 個空位，將其填入 val，並將該葉子 sum 設為 0，向上更新祖先節點的 sum。

查找第 k 個空位邏輯

void update(int o, int L, int R, int k, int val) {
    if (L == R) { sum[o] = 0; ans[L] = val; return; }
    int mid = (L + R) >> 1;
    if (k <= sum[o<<1]) update(o<<1, L, mid, k, val);
    else update(o<<1|1, mid+1, R, k - sum[o<<1], val);
    sum[o] = sum[o<<1] + sum[o<<1|1];
}

完整 C++ 代碼

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 200005;
int sum[MAXN << 2];
int ans[MAXN];
int p[MAXN], v[MAXN];

void build(int o, int L, int R) {
    if (L == R) { sum[o] = 1; return; }
    int mid = (L + R) >> 1;
    build(o<<1, L, mid);
    build(o<<1|1, mid+1, R);
    sum[o] = sum[o<<1] + sum[o<<1|1];
}

void update(int o, int L, int R, int k, int val) {
    if (L == R) { sum[o] = 0; ans[L] = val; return; }
    int mid = (L + R) >> 1;
    if (k <= sum[o<<1]) update(o<<1, L, mid, k, val);
    else update(o<<1|1, mid+1, R, k - sum[o<<1], val);
    sum[o] = sum[o<<1] + sum[o<<1|1];
}

int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        build(1, 1, n);
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &p[i], &v[i]);
            p[i]++; // 題目 p_i 從 0 開始，轉為 1-based
        }
        for (int i = n; i >= 1; --i) {
            update(1, 1, n, p[i], v[i]);
        }
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", ans[i], i==n?'\n':' ');
        }
    }
    return 0;
}

複雜度

建樹 O(n)，每次更新 O(log n)，共 n 次，總時間 O(n log n)，空間 O(n)。適合 n ≤ 200,000。