整体二分

参考资料

• 整体二分 - OI Wiki

简介

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

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

例题

洛谷 P3527 [POI 2011] MET-Meteors

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