整体二分浅谈

浅浅的总结一下简单情况。

适用范围

可以使用整体二分解决的题目需要满足以下性质：

• 询问的答案具有可二分性
• 修改对判定答案的贡献互相独立，修改之间互不影响效果
• 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
• 贡献满足交换律，结合律，具有可加性
• 题目允许使用离线算法

许昊然《浅谈数据结构题几个非经典解法》

一般来说适用于二分时每次 check 都要预处理，同时预处理代价较大的情况。

把所有询问一起二分，对于一个 check 就只需要预处理一次。

特殊情况的处理

查询

比如区间第 $k$ 小，就和平衡树上类似的，如果不在 $[l,mid]$ 里的，$k$ 要减去 $[l,mid]$ 小于它的个数。

修改

把修改和询问都视为操作（修改要满足上面的性质）。

比如带修改区间第 k 大，修改为把 $x$ 位置上的数改成 $y$，当 $mid\geq y$ 时用树状数组在 $x$ 这里 $-1$ 表示删除。

二维化

把初始的的都视作修改就能轻松处理。

类似 P1527 [国家集训队] 矩阵乘法。

优化

相比每次都撤销 $[l,mid]$ 内的所有预处理，维护一个 $p$ 表示 $[1,p]$ 已经被预处理，然后类似莫队的区间移动去把 $p$ 移动到 $mid$，这样加入和撤销的次数会少一半。

然后有些预处理操作不用撤销可以换成区间操作，就能少一个 $\log$。