学习报告-论对“整体二分”的新理解

二分我们都知道，我们一般会通过二分具有单调性的答案来找到一个最接近某个点的答案。

我们可能在以后的学习中遇到一些题，其答案是具有单调性的，但是如果让你在下面构造一个序列，或者构造一些答案，这些答案是无法二分的，只能“根据答案求过程”。然而当我们求出答案以后，再把这个过程凑出来如何容易！而且如果没有过程，我们也不能求出答案。这就引入了整体二分。

整体二分的作用场景：在询问许多区间的时候，如果对于每个询问都二分，时间复杂度是 \(O(Qn \log n)\) 的，必然会 \(\color{Blue}\texttt{TLE}\)，但是如果我们运用预处理的思想，把所有询问离线存储，一次二分解决所有问题，时间复杂度 \(O(n\log n)\)，就可以通过。

欸，我们看到了两个关键词：区间，二分。区间使我们联想到线段树，线段树使我们联想到分治，分治使我们联想到 \(O(\log n)\)，而二分也是 \(O(\log n)\) 的。这是不是说明，整体二分的时间复杂度约为 \(O(n\log^2 n)\)？

其实不然。如果是那样的话，我们实质上还是对每个区间做了分别操作，时间还是不会低于 \(O(Qn\log n)\)。真正的整体二分是边二分边分治，时间复杂度 \(O(n\log n)\)。

具体怎么做呢？我们设当前正在处理的区间为 \([L,R]\)，当前区间的值域为 \([l,r]\)，我们二分的时候把询问区间按照其某个性质与 \(mid\) 的关系排序，\(>mid\) 的放一边，\(\le mid\) 的放一边，然后再递归处理。

好，回到我们的引入。为什么我们说，有一些答案具有单调性的构造（序列）题也可以使用整体二分？这是因为序列实际上可以看成很多很多的区间，很多很多的区间又可以看成互不干涉的区间查询，最后我们把这些区间的答案依个输出，得到整体的答案。所以很多整体二分题一般不会把区间询问摆在明面上，而是伪装成构造题让我们解答。当我们发现某些构造题的最优答案具有单调性——要注意了——这很可能就是整体二分。