在遇到某些单个询问可以用二分解决的问题时，面对多组询问，我们思考如果能够对所有询问一并二分解决的话就可以解决整个问题。这时候，整体二分便会成为我们有力的工具。

整体二分是一种离线思想，通过将多组询问同时处理以达到很好的时间复杂度，下面我们以下面几个例子来学习。

📝 NOTE 有一个长为 的序列 ，现在有 组询问，每组询问整个序列中第 小的值是多少。

， ， 。

如果直接排序的话，这道题显然是简单的，那我们思考我们能否使用二分的方式解决单个询问呢?

考虑二分答案，已知 ，说明答案肯定也在 之内。不妨二分 ，统计整个序列中小于等于 的数的个数，若其大于等于 ，说明最终答案一定小于等于 ，则 ，否则 。若 ，则说明答案为 。

那么我们如果能同时处理所有询问就好了，不难发现，在第一次求 时，我们可以同时处理出所有询问答案和 的关系。那么我们可以把询问分为两类： 和 。若对两类继续如此递归，复杂度肯定会爆炸。不过我们发现，在二分询问的过程中，我们同样也可以二分 。

• 若 ，则我们只需要在 的数中统计即可，因为在下一次二分中的数一定小于 ，显然 的 不可能被统计入答案。

• 若 ，设 表示 的 的数量。则我们知道下一次统计当中在这一次被统计进入的数下一次一定还会被统计，所以不妨令 ，这时候我们只需要在 中的 继续递归即可。

通过这样的做法， 也被不停的二分到不同的区间内，且最多被分到 个区间内，其中 是值域。而 在每个区间内只会被统计到一次，那么总统计次数就是 的。这样我们就在 的时间复杂度内解决了这个问题。

📝 NOTE 有一个长为 的序列 ，现在有 组询问，每组询问有三个参数 ，表示询问序列 中 的区间第 小值。

， ， ， 。

这一道题目当中我们显然不可能再进行排序后直接完成了，通常采用的是可持久化线段树来完成，不过也有使用整体二分的做法。

类似之前的做法，只不过之前的题目可以看成各组询问的 。所以我们在之前的题目中在每个被二分到的区间内每个数只需要被遍历到一次。而如果这道题目我们采用同样的策略，肯定会超时，考虑怎么优化。

发现我们只需要把小于等于 的位置从直接统计改成在数状数组上 ，然后通过简单的查询就能得到每组区间的答案，这样我们就解决了这个问题。

注意清空数状数组不要直接 memsetmemset，可以在数状数组中反着做一遍来实现清空。

同样每个数会被访问到 次，单次在数状数组上修改的复杂度为 ，查询总复杂度为 ，若 同阶，则总复杂度可表示为 。

💡 TIP 如果带修改呢？我们还可以这样完成吗？

实际上，我们只需要能够正确统计出以上信息，修改就并不会造成影响。

对于修改操作，我们可以看成若数状数组中原下标已经有 11，则把原下标位置减去，然后再研究修改后的数是否小于等于 ，如果是则在数状数组上 ，只要我们能保证我们按照顺序做，那么正确性就可以保证。不过第一步记忆是否有 11 还是稍显麻烦，而且若更改操作和原操作没有被分配到同一个区间，还会导致我们不知道原操作的 11 什么时候被删除，所以不妨把一次修改操作改成删除操作和添加操作，删除的下标所对应的值是原值，增加的是新值。显然只有原值小于等于 时，我们才会进行删除操作，可以说明这样是正确的。

📝 NOTE 题目大意：

给定一颗有 个点的树，现在有三种操作：

1. 添加一条路径
2. 删除一条已经被添加的路径
3. 在未删除的路径中查询不经过点 的路径的最大权值

一共操作 次。

， 。

与上一道题类似的思路，我们肯定首先要选择二分答案，问题是，我们如何判断答案是否可达呢？

发现我们其实可以这样做：二分出一个值 midmid，如果路径权值 midmid，就在对应路径上的所有点权 ，并且定义变量 tottot，如果新增一条路径 tot++tot++，反之在删除时路径上点权 ，tot--tot--。对于每一次查询，只需要查找当前点点权，就可以得到有多少条路径经过它，再用 tottot 减掉刚刚的结果，便可知在不经过他的路径中是否有权值 midmid 的了。

考虑如何快速在树上进行操作，因为子树 dfs 序连续，所以我们可以直接在树状数组上进行操作，具体而言，设路径端点为 ，则我们在 的权值 ， 以及其父亲的权值 。单点查询时，只需要查询这个点对应的子树即可。

每一个询问最多被分到 个区间内，在单区间内每个询问在树状数组上以 的复杂度被修改，共有 个询问，若 同阶，则总复杂度 。

📝 NOTE 题目大意： 有 家书虫食品店，有 个家庭来享受用书虫制作的美味食物。

因为食品店十分火爆，所以顾客需要排队，刚开始所有队列都是空的。

今天食品店又全部开张了，发生了 个事件：

• 加入事件：编号位于区间 内的所有食品店中，都有编号为 的家庭加入队尾，每个满足要求的食品店队尾都加入了 个人。
• 离开事件：编号位于区间 内的所有食品店中，如果队列有超过 个人，那么队列的前 个人离开队列，否则队列里的所有人离开队列。
• 白嫖事件：如果编号为 的食品店的队列中有大于等于 个人，那么食品店就会赠送从队列开头开始数第 个人一份秘制书虫，否则店员会吃掉书虫。

求每次 白嫖事件 是否有顾客被赠送了秘制书虫，如果有的话，求顾客所在的家庭。

， ， 。

看起来似乎这一道题目和整体二分并没有什么关系，不过若没有离开事件，则我们不妨可以二分前多少个事件加入后（同时要求这些事件发生在白嫖事件前），队列里的元素数量大于 ，不妨设队列元素数量为 ，则若 ，说明能被赠送书虫的家庭加入的时间小于等于队列元素数量为 的时间，否则大于，这样我们就可以用整体二分解决了。

若存在删除事件，容易发现我们可以对每个队列统计删了多少个，设其为 del[i]del[i]，则 B[j]=del[A]+B[j]B[j]=del[A]+B[j]。del[i]del[i] 可以用一个线段树通过合理的下传标记来维护。

若 同阶，则时间复杂度 。