HDU 4417 Super Mario：劃分樹解決區間第 K 大

問題大意

長度 n≤1e5 序列，m≤1e5 查詢：區間 [L,R] 中 ≤ H 的數個數。等價於查詢第 k 大與 H 比較，k 為二分搜尋。

劃分樹原理

• 構建：遞迴將區間按中位數分為左右，記錄每層每個位置屬於左子樹的個數 lftnum 及左子樹值 lfts（可求和）。
• 查詢：在第 k 大查詢中，根據 lftnum 決定下降左或右子樹，同步累加左子樹元素和。

代碼框架

void build(int L,int R,int dep) {
    if (L==R) return;
    int mid=(L+R)>>1, key=val[mid], lcnt=mid-L+1;
    // 統計 = k) return query(左子樹區間, dep+1, k);
    else return query(右子樹區間, dep+1, k-cnt);
}

應用本題

二分 k ∈ [1, R-L+1]，利用 query 取第 k 大值與 H 比較，最終得到 ≤ H 的最大 k 即為答案。