Skip to main content

整体二分

Summary

整体二分把多个询问的答案放在一起同时二分。每层取当前答案值域的中点，扫描这一层的修改与询问，按只计入不超过中点的贡献时是否已经满足条件分成两组，再递归处理左右值域。它适用于答案可二分判定、修改可以离线且贡献能够累计的问题，典型应用是多次询问区间第 k 小。总复杂度通常为 O((n+q)lognlogV)，例题为洛谷 P3527。

参考资料​

简介​

整体二分 把多个询问的答案放在一起二分。对当前答案值域 [l,r][l,r] 取 midmid，扫描这一层的所有修改与询问，按「在只考虑 ≤mid\le mid 的贡献下是否已满足」把它们分成两组，分别递归到 [l,mid][l,mid] 与 [mid+1,r][mid+1,r]。

它适用于「答案可二分判定、修改可离线、贡献可用树状数组等结构累计」的问题，如多次询问区间第 kk 小。总复杂度通常为 O((n+q)log⁡nlog⁡V)O((n+q)\log n\log V)。

例题​

洛谷 P3527 [POI 2011] MET-Meteors

环形排列的 mm 个区域各属于某个国家，共 nn 个国家，国家 ii 的目标产量为 pip_i。依次发生 qq 次流星雨，每次令环上一段连续区域各增产若干。对每个国家，求它最早在第几次流星雨后累计产量达到目标。