整体二分

本文通过介绍几道例题的解法，带你深入了解整体二分的精髓。

例题

大致按难度排序，其中，中间的三道题都是类似的。

• P3527 [POI2011] MET-Meteors
• P3332 [ZJOI2013] K大数查询
• P2617 Dynamic Rankings
• P1527 [国家集训队] 矩阵乘法
• P5163 WD与地图

简介

给你 \(Q\) 个询问，每个询问形如第 \(k\) 小是什么或某个点什么时候符合所给条件（达到一定数量），中间可能带有修改，并且不强制在线。

一般来说，如果 \(Q\) 个询问可以分别每次用二分的方式求答案，那么我们可以把这 \(Q\) 次询问合在一起做一个分治递归，这就是整体二分。

多说无用，直接看例题。

P3527 [POI2011] MET-Meteors

我们要求每个国家在什么时间满足条件，所以二分时间。

我们设 \(solve(l,r,S)\)，表示已知 \(S\) 这个集合中每个国家的答案都在 \([l,r]\) 的区间内，然后求出它们具体的时间。

设 \(mid=\lceil{\dfrac{l+r}{2}\rceil}\)。

我们可以把时间在 \([l,mid]\) 的修改执行。

之后判断 \(S\) 中的每个国家，是否已满足条件，是则说明它的答案在 \([l,mid]\) 内，否则在 \([mid+1,r]\) 内。

我们可以新建两个 vector 把 \(S\) 分掉，然后往两边递归。

考虑右区间 \([mid+1,r]\) 需要用到 \([l,mid]\) 修改的贡献，所以可以这样：

• 先递归右区间 \([mid+1,r]\)。
• 清除 \([l,mid]\) 修改的共线。
• 递归左区间 \([l,mid]\)。

我们可以用树状数组处理修改带来的贡献。

考虑复杂度，默认各数据同阶。

最多往下递归 \(O(\log n)\) 层。

对于每个时间的修改，它在每层都出现，而在树状数组上修改贡献是 \(O(\log n)\) 的。每个时间的修改的总数是 \(O(n)\) 的，于是修改是 \(O(n\log ^2n)\) 的。

对于查询，一个国家在每层出现一次，每次 \(O(\log n)\) 查询，于是也是 \(O(n\log^2n)\) 的。

总复杂度 \(O(n\log ^2n)\)。

注意到这题的修改和查询没有什么其他限制，我们可以把树状数组换成差分，然后扫一遍即可，然后要记录每个国家当前的贡献和修改前的贡献，复杂度降为 \(O(n\log n)\)。