[离线技巧] 整体二分

来介绍一下整体二分。

整体二分需要满足一下条件：

• 问题之间独立
• 可以离线
• 具有单调性答案
• 贡献可合并

我们通过几个例子，通俗的理解这个算法。

问题 \(1\)

给定 \(n\) 个数，求第 \(k\) 小。

我们思考这个问题怎么做。
不用排序，显然，答案具有单调性。
那么，我们可以二分一个答案，判断有多少个数小于等于当前的数，求出排名，然后得出答案。

时间复杂度 \(O(n\log w)\)

问题 \(2\)

给定 \(n\) 个数， \(q\) 次询问第 \(k_i\) 小。

我们考虑每个询问都二分答案，前缀和处理出所有数出现个数(不是，都排序了，为什么要这样搞)，判断即可。
时间复杂度 \(O((n+q)\log n)\)

问题 \(3\)

给定 \(n\) 个数，求区间 \([l,r]\) 第 \(k\) 小。\(q\) 次询问。

这是主席树经典问题。
我们考虑二分解决。
对于第 \(k\) 次询问，我们二分答案，把所有小于等于 \(mid\) 的数打上标记，看看 \([l,r]\) 内有多少个打标记的数即可。

时间复杂度 \(O(nq\log w)\) 很明显，这超时了。

我们发现瓶颈在每次都打一次标记。于是整体二分思想就出来了，整体二分一个 \(mid\) ，然后把所有 \(\forall x\le mid\) 都打上标记，然后对于一个询问是否合法，区间查询个数，然后扔成 \([l,mid]\) 和 \([mid+1,r]\) 两部分处理即可。

这就是整体二分的思想，它的妙处是每次处理询问，操作，时间复杂度都是 \(O(n+q)\log q\) ，瓶颈在于各种操作，例如这题，瓶颈在于区间查询，使用树状数组即可 \(O(n\log^2 n)\) 解决问题。

问题 \(4\) Dynamic Rankings

给定 \(n\) 个数，求区间 \([l,r]\) 第 \(k\) 小，或将 \(a_x\) 修改为 \(y\)。\(q\) 次询问。

按照时间处理询问即可。
具体的，将修改数变为在某个地方加减一个 \(1\) 。
递归处理所有询问即可。

总结一下，对于整体二分，他的适用情况是将原来二分的问题拆开成若干询问，将 \(check(mid)\) 的时间复杂度均摊。

所以，对于整体二分的贡献处理有几种方法。
第一种是像 \(kth\) 小那样，直接消除另一个区间的贡献，问题 \(4\) 就是例题。
另一种是考虑到另一个区间没有贡献，直接不管即可，例题是 This.
还有一种是直接处理完另一半区间后再数据结构上加上这一部分贡献，这个只能静态的搞，\(kth\) 可以靠这个优化成 \(O(n\log n)\) ，例子是 .this

最后，能用小常数 BIT 就尽量用。