BZOJ 3110 [ZJOI2013] K大數查詢 —— 線段樹套線段樹 + 二分答案（主席樹前身）

BZOJ 3110：N, M ≤ 50000，兩種操作：

1. 區間加值：[a, b] 每個位置插入數 c
2. 區間第 K 大：查詢 [a, b] 中第 c 大的數

經典線段樹套線段樹（權值線段樹外層，區間線段樹內層）+ 二分答案，也是主席樹（可持久化線段樹）的非持久化版本。

一、數據結構設計

• 外層：權值線段樹，節點覆蓋值域 [L, R]。
• 內層：每個外層節點掛一棵區間線段樹，維護該值域內數字在序列位置 [1, N] 的出現次數。
• 動態開點：tot 計數，ls[], rs[], sum[], tag[]（懶標記）。

二、核心操作

1. 內層區間加值

void add(int &k, int l, int r, int a, int b) {
    if (!k) k = ++tot;
    if (l == a && r == b) { tag[k]++; sum[k] += r-l+1; return; }
    pushdown(k, l, r);
    int mid = (l+r)>>1;
    if (b <= mid) add(ls[k], l, mid, a, b);
    else if (a > mid) add(rs[k], mid+1, r, a, b);
    else add(ls[k], l, mid, a, mid), add(rs[k], mid+1, r, mid+1, b);
    pushup(k);
}

2. 外層插入：沿值域路徑更新所有覆蓋節點

void insert() { // 全局 a,b,c 為位置區間與值
    int k = 1, l = 1, r = N;
    while (l != r) {
        add(rt[k], 1, N, a, b); // 當前值域節點的內層樹加 1
        int mid = (l+r)>>1;
        if (c <= mid) { r = mid; k = k<<1; }
        else { l = mid+1; k = k<<1|1; }
    }
    add(rt[k], 1, N, a, b); // 葉子節點也要加
}

3. 查詢：二分答案

int solve() { // 查詢 [a,b] 第 c 大
    int k = 1, l = 1, r = N;
    while (l != r) {
        int mid = (l+r)>>1;
        int rightCnt = query(rt[k<<1|1], 1, N, a, b); // 右子樹（大值）計數
        if (rightCnt >= c) { l = mid+1; k = k<<1|1; }
        else { c -= rightCnt; r = mid; k = k<<1; }
    }
    return l;
}

三、複雜度分析

• 單次插入：O(log N · log N)（外層高度 × 內層更新）。
• 單次查詢：O(log N · log N)（二分 log N 步，每步內層查詢 log N）。
• 空間：動態開點，最多 O(M log² N) 節點，maxn ≈ 2×10⁷ 稍大，需靜態數組 + -O2。

四、工程優化

1. 用 inline、快速輸入、static 數組。
2. 內層 pushdown 只在非葉子且有標記時創建子節點。
3. 若時限極緊，改用主席樹（可持久化線段樹）單棵樹解決，無需套樹，常數更小。