引入
首先来看一个经典问题：【模板】可持久化线段树 2（主席树）（静态区间第 (k) 小）
抛开主席树的做法，仔细审视这个问题的答案可以发现其实是有单调性的。
因此对于一个询问，可以考虑先二分答案再统计区间内不大于其的数的个数，复杂度 (mathcal{O(qn log n)}) 不能接受。
但注意到统计过程中有很多询问是重复的，那么能否将这些重复的统计去除呢？
一个可行的想法就是将所有询问先离线然后依据询问间的特性进行整体二分。
经典问题
还是上面那个问题，下面给出该问题的整体二分解法。
首先还是在值域上二分答案 (mid)，想办法处理出所有询问在 ( t check) 该值时返回的结果。
不难发现可以直接对于每个 (le mid) 的数在序列中的位置 (+1)，接下来对于每个询问查询区间内 (1) 的个数即可，使用树状数组可以轻松解决，复杂度 (mathcal{O((n + q) log n)})。
此时所有询问将被分为两个集合，分别为答案 (le mid, > mid) 的两个部分，我们直接递归下去，最终直到值域为 ([x, x]) 即可得到答案。
此时仔细分析复杂度，不难得到为：(mathcal{O(n ^ 2 log n + q log ^ 2 n)}) 还是难以接受。
由复杂度分析可知，瓶颈在于对于每个询问集合，都要将整个序列的元素插入树状数组，能否避免这个情况呢？
不难发现只要使得递归同深度插入元素之和为 (mathcal{O(n)}) 即可。
那么由于该问题的特性，在一次分集合的过程中，对于答案 (> mid) 的询问，此时求出的区间内 (le mid) 的数之后均会产生贡献，这部分计算是不必要的。
因此我们仅需将这个集合的询问 (k) 减去当前区间内 (le mid) 的数，然后将原序列 (> mid) 的数与其一起往下递归即可。
此时复杂度 (mathcal{O((n + q) log ^ 2n)})。
请注意，该问题的空间复杂度是线性的，请不要图方便直接递归两个 ( t vector) 这样又慢空间又不对。
具体地，我们在实现将集合划分成两个部分时，只需将其划分到原询问序列的两个区间，然后向下传两个区间的左右端点即可。
同时为了方便可以直接将原序列的元素和询问序列合并这样递归更为方便。
一般要求及解法
由上面那个经典问题，我们可以发现整体二分可以应用的几点要求（不带修）：
- 题目可以支持二分。
- 所求答案满足单调性，可以二分。
- 元素对询问的贡献具有可加性，且询问元素之间具有独立性。
同时也可以发现它的基本运行流程：
-
首先将询问离线，在值域上二分答案。
-
使用数据结构维护当前元素对询问的贡献，依据判定标准将询问分为两个集合。
-
将接下来的冗余贡献先加上，同时将所有元素也分为两个集合。
-
将分成的两个集合递归，边界为二分答案边界。
经典解法的优化
主席树都是 (mathcal{O((n + q) log n)}) 的且可以支持在线，那么整体二分也可以做到 (mathcal{O(n + q) log n}) 吗？
答案是可以的。
不难发现由于整体二分的特性，若要支持一个 (log) 那么只能在数据结构维护方面下功夫。
仔细观察树状数组维护了什么：
- 单点修改，区间查询，同时所有修改在询问之前。
借助询问在修改之前的特性，这个问题可以直接差分解决。
但需要注意的是，由于需要保证每个区间涉及元素不超过询问 + 修改元素个数，因此我们需要提前将询问拆成两个，只对有效的单点求前缀和即可。
实现是可以在一开始就将询问拆成两个，然后将这两个询问标号并将一个贡献设置为 (1) 一个为 (-1)。
同时将修改和询问放在同一个序列中，按照在原序列中的下标的大小排好序。
整体二分时直接扫描并维护前缀和即可，递归时为了保证依然有序依次分为两个集合。
由此，该经典问题有了一个时间 (mathcal{O((n + q) log n)}) 空间 (mathcal{O(n + q)}) 的 离线做法。
待修改的整体二分
大体上与不带修的做法类似，做出了如下改动：
-
将修改看作将之前的贡献减去，在将新的贡献加上。
-
将原序列的元素贡献也看作修改（操作时间看作 (0)），意义与前一条一致。
-
将询问和修改放到同一个序列中，按照操作时间排序。
由于多了一，三条限制，因此待修改的整体二分多出了三条要求：
- 修改对判定答案的贡献相互 独立
- 若修改对判定答案存在贡献，该贡献与询问无关
- 修改的顺序必须按照时间进行，不能进行进一步排序
由于限制 (3)，可知静态问题的优化在动态问题上不生效。
因此整体二分解决动态区间第 (k) 小问题时间复杂度 (mathcal{O((n + q) log ^ 2n)})，空间复杂度 (mathcal{O(n + q)})，相较于传统的树套树，码量小且空间复杂度优。