HDU 5412：區間第 K 大（整體二分 + 樹狀數組）

題目大意

• 初始序列 n 個數。
• 兩種操作（共 q 次）：
   1 l v：將第 l 個數改為 v。
   2 l r k：查詢區間 [l, r] 第 k 大值。
• n, q ≤ 10⁵，數值 ≤ 10⁹。

整體二分核心思想

將「數值域」與「操作序列」綁定，遞歸二分數值域 [L, R]：

1. 中點 mid = (L+R)/2。
2. 掃描當前操作列表：
    - 修改操作：若 v ≤ mid，視為「生效」，在樹狀數組加 +1；否則「不生效」。
    - 查詢操作：用樹狀數組求區間內「生效」元素個數 cnt。
     若 cnt ≥ k，答案在左半部 [L, mid]，保留 k 不變。
     若 cnt < k，答案在右半部 [mid+1, R]，更新 k -= cnt。
3. 按原順序將操作分流到左右兩組，遞歸處理。
4. 當 L == R 時，所有查詢的答案即為 L。

關鍵細節

• 修改操作拆分為「刪除舊值」+「插入新值」兩條記錄，類型分別為 -1 和 +1，樹狀數組加減對應類型值。
• 分流時必須保持操作相對順序，使用雙指針 l, r 從兩端向中間填充臨時數組 id2，再拷回 id1。
• 遞歸結束後需清理樹狀數組（將本層加入的修改減回去）。

完整代碼

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

const int MAXN = 300010;
struct Op {
    int type; // 1: add, -1: del, 2: query
    int l, r, v, ans;
} ops[MAXN];
int bit[MAXN], n, q, tot, maxVal;
int id1[MAXN], id2[MAXN];
int a[MAXN];

int lowbit(int x) { return x & -x; }
void addBIT(int i, int v) { for (; i <= n; i += lowbit(i)) bit[i] += v; }
int sumBIT(int i) { int s = 0; for (; i; i -= lowbit(i)) s += bit[i]; return s; }

void solve(int L, int R, int valL, int valR) {
    if (L > R) return;
    if (valL == valR) {
        for (int i = L; i <= R; ++i)
            if (ops[id1[i]].type == 2) ops[id1[i]].ans = valL;
        return;
    }
    int mid = (valL + valR) >> 1;
    int left = L, right = R;
    for (int i = L; i <= R; ++i) {
        Op &o = ops[id1[i]];
        if (o.type == 2) {
            int cnt = sumBIT(o.r) - sumBIT(o.l - 1);
            if (cnt < o.v) {
                o.v -= cnt;
                id2[right--] = id1[i];
            } else {
                id2[left++] = id1[i];
            }
        } else {
            if (o.v <= mid) {
                addBIT(o.l, o.type);
                id2[left++] = id1[i];
            } else {
                id2[right--] = id1[i];
            }
        }
    }
    for (int i = L; i <= R; ++i) {
        Op &o = ops[id1[i]];
        if (o.type != 2 && o.v <= mid) addBIT(o.l, -o.type);
    }
    for (int i = L; i < left; ++i) id1[i] = id2[i];
    for (int i = left, j = R; i <= R; ++i, --j) id1[i] = id2[j];
    solve(L, left - 1, valL, mid);
    solve(left, R, mid + 1, valR);
}

int main() {
    while (scanf("%d", &n) == 1) {
        memset(bit, 0, sizeof(bit));
        tot = maxVal = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            ops[tot] = {1, i, i, a[i], 0};
            id1[tot] = tot;
            maxVal = max(maxVal, a[i]);
            ++tot;
        }
        scanf("%d", &q);
        while (q--) {
            int tp; scanf("%d", &tp);
            if (tp == 1) {
                int l, v; scanf("%d%d", &l, &v);
                ops[tot] = {-1, l, l, a[l], 0}; id1[tot] = tot; ++tot;
                a[l] = v;
                ops[tot] = {1, l, l, a[l], 0}; id1[tot] = tot; ++tot;
                maxVal = max(maxVal, v);
            } else {
                int l, r, k; scanf("%d%d%d", &l, &r, &k);
                ops[tot] = {2, l, r, k, 0}; id1[tot] = tot; ++tot;
            }
        }
        solve(0, tot - 1, 0, maxVal);
        for (int i = 0; i < tot; ++i)
            if (ops[i].type == 2) printf("%d\n", ops[i].ans);
    }
    return 0;
}

複雜度分析

• 數值域二分深度 O(log V)，V ≤ 10⁹ 約 30 層。
• 每層掃描所有操作 O((n+q) log n)（樹狀數組單次 O(log n)）。
• 總時間 O((n+q) log n log V)，空間 O(n+q)。