整体二分

引入

在信息学竞赛中，有一部分题可以使用二分的办法来解决。但是当这种题目有多次询问且每次询问我们对每个查询都直接二分，可能会收获一个 TLE。这时候我们就会用到整体二分。整体二分的主体思路就是把多个查询一起解决。（所以这是一个离线算法）

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

1. 询问的答案具有可二分性

2. 修改对判定答案的贡献互相独立，修改之间互不影响效果

3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值

4. 贡献满足交换律，结合律，具有可加性

5. 题目允许使用离线算法

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

解释

记 为答案的值域， 为答案的定义域。（也就是说求答案时仅考虑下标在区间 内的操作和询问，这其中询问的答案在 内）

• 我们首先把所有操作 按时间顺序 存入数组中，然后开始分治。
• 在每一层分治中，利用数据结构（常见的是树状数组）统计当前查询的答案和 之间的关系。
• 根据查询出来的答案和 间的关系（小于等于 和大于 ）将当前处理的操作序列分为 和 两份，并分别递归处理。
• 当 时，找到答案，记录答案并返回即可。

需要注意的是，在整体二分过程中，若当前处理的值域为 ，则此时最终答案范围不在 的询问会在其他时候处理。

过程

注：

1. 为可读性，文中代码或未采用实际竞赛中的常见写法。
2. 若觉得某段代码有难以理解之处，请先参考之前题目的解释， 因为节省篇幅解释过的内容不再赘述。

从普通二分说起：

查询第 k 小：一次二分多个询问

题 1 在一个数列中查询第 小的数。

当然可以直接排序。如果用二分法呢？可以用数据结构记录每个大小范围内有多少个数，然后用二分法猜测，利用数据结构检验。

题 2 在一个数列中多次查询第 小的数。

可以对于每个询问进行一次二分；但是，也可以把所有的询问放在一起二分。

先考虑二分的本质：假设要猜一个 之间的数，猜测之后会知道是猜大了，猜小了还是刚好。当然可以从 枚举到 ，但更优秀的方法是二分：猜测答案是 ，然后去验证 的正确性，再调整边界。这样做每次询问的复杂度为 ，若询问次数为 ，则时间复杂度为 。

回过头来，对于当前的所有询问，可以去猜测所有询问的答案都是 ，然后去依次验证每个询问的答案应该是小于等于 的还是大于 的，并将询问分为两个部分（不大于/大于），对于每个部分继续二分。注意：如果一个询问的答案是大于 的，则在将其划至右侧前需更新它的 ，即，如果当前数列中小于等于 的数有 个，则将询问划分后实际是在右区间询问第 小数。如果一个部分的 了，则结束这个部分的二分。利用线段树的相关知识，我们每次将整个答案可能在的区间 划分成了若干个部分，这样的划分共进行了 次，一次划分会将整个操作序列操作一次。若对整个序列进行操作，并支持对应的查询的时间复杂度为 ，则整体二分的时间复杂度为 。

试试完成以下代码：

参考代码如下

区间查询第 k 小：对只询问指定区间的处理

题 3 在一个数列中多次查询区间第 小的数。

涉及到给定区间的查询，再按之前的方法进行二分就会导致 check 函数的时间复杂度爆炸。仍然考虑询问与值域中点 的关系：若询问区间内小于等于 的数有 个，询问的是区间内的 小数，则当 时，答案应小于等于 ；否则，答案应大于 。（注意边界问题）此处需记录一个区间小于等于指定数的数的数量，即单点加，求区间和，可用树状数组快速处理。为提高效率，只对数列中值在值域区间 的数进行统计，即，在进一步递归之前，不仅将询问划分，将当前处理的数按值域范围划为两半。

参考代码（关键部分）

下面提供 【模板】可持久化线段树 2（主席树） 一题使用整体二分的，偏向竞赛风格的写法。

带修区间第 k 小：整体二分的完整运用

题 4 Dynamic Rankings 给定一个数列，要支持单点修改，区间查第 小。

修改操作可以直接理解为从原数列中删去一个数再添加一个数，为方便起见，将询问和修改统称为“操作”。因后面的操作会依附于之前的操作，不能如题 3 一样将统计和处理询问分开，故可将所有操作存于一个数组，用标识区分类型，依次处理每个操作。为便于处理树状数组，修改操作可分拆为擦除操作和插入操作。

优化

1. 注意到每次对于操作进行分类时，只会更改操作顺序，故可直接在原数组上操作。具体实现，在二分时将记录操作的 数组换为一个大的全局数组，二分时记录信息变为 ，即当前处理的操作是全局数组上的哪个区间。利用临时数组记录当前的分类情况，进一步递归前将临时数组信息写回原数组。
2. 树状数组每次清空会导致时间复杂度爆炸，可采用每次使用树状数组时记录当前修改位置（这已由 1 中提到的临时数组实现），本次操作结束后在原位置加 的方法快速清零。
3. 一开始对于数列的初始化操作可简化为插入操作。

关键部分参考代码

参考习题

「国家集训队」矩阵乘法

「POI2011 R3 Day2」流星 Meteors

参考资料

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