POJ 2104 K-th Number：線段樹合併（主席樹/可持久化線段樹）

問題描述

給定長度 n ≤ 100,000 的數組 a[1..n]（互不相同），m ≤ 5,000 個查詢 Q(i, j, k)：求區間 [i, j] 排序後第 k 小的數。數值絕對值 ≤ 10^9。

核心思路：主席樹（可持久化線段樹）

1. 將數組值離散化（排序去重），映射到 1..n 的排名。
2. 構建 n 棵線段樹版本 root[i] 表示前綴 [1..i] 的值頻率統計。root[i] 由 root[i-1] 插入 a[i] 得到，只新建 O(log n) 個節點，共享其餘。
3. 查詢 [l, r] 第 k 小：利用 root[r] - root[l-1] 的差值，在線段樹上二分（比較左子樹計數與 k）。

線段樹結構

struct Node {
    int l, r;       // 左右孩子索引
    int cnt;        // 該區間元素個數
} tree[MAXN * 20];  // n log n 節點
int roots[MAXN];
int tot = 0;

構建與查詢

void insert(int& cur, int pre, int l, int r, int pos) {
    cur = ++tot;
    tree[cur] = tree[pre];
    tree[cur].cnt++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) insert(tree[cur].l, tree[pre].l, l, mid, pos);
    else insert(tree[cur].r, tree[pre].r, mid+1, r, pos);
}

int query(int u, int v, int l, int r, int k) {  // u=root[r], v=root[l-1]
    if (l == r) return l;
    int left_cnt = tree[tree[u].l].cnt - tree[tree[v].l].cnt;
    int mid = (l + r) >> 1;
    if (k <= left_cnt) return query(tree[u].l, tree[v].l, l, mid, k);
    else return query(tree[u].r, tree[v].r, mid+1, r, k - left_cnt);
}

完整流程

1. 讀入 n, m，數組 a。
2. 離散化：sorted = a，排序去重。
3. 構建主席樹：for i=1..n: insert(roots[i], roots[i-1], 1, n, rank(a[i]))。
4. 處理查詢：idx = query(roots[r], roots[l-1], 1, n, k)，輸出 sorted[idx]。

複雜度

• 構建：O(n log n) 時間，O(n log n) 空間（約 200 萬節點）。
• 查詢：O(log n)。
• 總計：O((n+m) log n)，完美應對 10 萬/5 千規模。

關鍵點

1. 值域大（10^9）必須離散化。
2. 線段樹節點池預分配，避免 new/delete 開銷。
3. 查詢利用版本差分，無需合併樹。