整体二分

不久前学了整体二分，做了几道题，还在考试上派上用场过几次。
觉得自己大概懂了整体二分，直到一次碰上了强制在线的毒瘤题。。。

整体二分：从离线到强制在线

基础

大概讲讲整体二分吧。

整体二分大概用于这样一个场景：
有多组询问，每个询问可以二分，但是每个询问二分的时间不能接受，
而不同询问的二分有共同点，这时就可以用整体二分把多个询问一起二分。
所以这是个离线算法。

流程大概是这样的：
对于当前确定的区间 [L, R] ，取 M 为区间中点，
对于当前在确定在这个区间的每个询问进行 check ，
然后判断每个询问接下来是到 [L, M] 还是 [M + 1, R] 。
当 L = R 时，就得到了处理到这个区间的询问的答案。

每个询问还是进行了 O(logV) 次 check ，
但是和直接二分不同的是，一般在每个区间内进行预处理后 check 可以做到 O(1) 或者 O(logn) 等，
一般需要数据结构维护（常见的有并查集，树状数组，线段树）。

栗子

就说静态区间第 k 大吧，当然可以用主席树搞，但是此处讨论整体二分。

对于每个询问 [l, r] ，可以二分答案 x ，
然后 check 不超过 x 的数量，与 k 进行比较即可得出接下来该询问的答案区间。

直接 check 是 O(V) 的，当然可以直接用数据结构维护，但是此处讨论整体二分。

当前的答案区间是 [L, R] ，有若干询问的答案已经确定在这个区间内，
取中点 M ，维护值在 [L, M] 的每个数，对于每个询问就可以 O(logn) check 了，
然后如果询问 k 的答案在 [M + 1, R] ，那么 k 要减去当前 check 的值，以消去 [L, M] 的影响。
另外处理后要清空 [L, M] 的影响。

这样做复杂度是 \(O(q logV logn)\) 的。

另一个实现是维护值在 [1, M] 的每个数，
二分到 [L, M] 前先把 [L, M] 的影响撤销掉，
二分到 [M + 1, R] 前只需在二分 [L, M] 时保证算上了 [L, M] 的贡献即可。
这样做的好处是避开了删除，有些用并查集的操作就可以实现了。

这样做复杂度同样是 \(O(q logV logn)\) 的。

带修

就说带修区间第 k 大。

将修改和查询统称为操作，只需保证操作在二分中的相对顺序，
处理答案在 [L, R] 的区间时按顺序做，碰到修改就修改，碰到查询就 check 。
但是修改哪来的答案？对于修改操作，只需将它放到它能影响的答案区间即可。
例如修改 \(a_i = x\) ，分为两个操作：删除 \(a_i\) 和添加 \(a_i = x\) 。
前者的影响的区间需要包括 \(a_i\) ，后者影响的区间需要包括 \(x\) 。

同样有两个实现，复杂度都是 \(O(q logV logn)\) 。

在线

毒瘤的地方来了，整体二分做强制在线。
这也是本文的真正讨论重点。

还是拿静态区间第 k 大分别讨论上述的两种实现。

实现 1

单独考虑一个询问 q ，观察它在整体二分中答案区间的移动过程。
假设当前二分到区间 [L, R] ，
q 能在整体二分中 O(logn) check 是因为权值在 [L, R] 的数被维护进了一个数据结构。
那如果 q 到达的所有可能答案区间的数据结构都提前构造好了，
q 就不需要整体二分，而可以直接在线询问。

而所有可能的答案区间事实上形成了一个线段树的结构。
上面已经说到要求每个可能的答案区间的数据结构已经提前维护。
对应在线段树中就是线段树的每个节点都有数据结构维护该节点对应的答案区间。
在本题中就是要权值线段树套区间树状数组，
而为了节省空间开销，需要换成权值线段树套区间线段树。
这样把每个数先按取值找到对应的外层线段树，再按位置加到对应的内层线段树，
每个询问 (l, r, k) 就在外层线段树上二分，在内层线段树查询区间 [l, r] 的数的个数。

时间复杂度依然是 \(O(q logV logn)\) 的，但是空间复杂度为 \(O(V + n logV logn)\) 。

不难推广到更一般的情况，所有不带修的整体二分实现 1 + 数据结构 A， 都可以用线段树套数据结构 A 做到在线询问。
时间复杂度不变，但是空间开销会乘上 \(O(n)\) ，
而当数据结构 A 支持动态开空间，即空间开销与修改次数 \(q\) 成函数关系 \(O(qk)\) 时，
这样就只会带来 \(O(n logV k)\) 的额外空间开销。

另外，这是可以支持带修的，对于修改操作，在线段树上找到影响的节点，
然后直接去修改节点上的数据结构 A 即可。

实现 2

还是单独考虑一个询问 q ，此时它在整体二分中答案区间的移动过程固然还是线段树的形式。
但是不同的是，此时线段树的每个节点 [L, R] 需要保存维护 [1, R] 的数据结构，
换言之，不同节点之间相互不独立。
但既然所有需要的数据结构都是维护 [1, K] 这样的前缀形式，
不难想到可持久化，每个维护 [1, K] 的数据结构在维护 [1, K - 1] 的数据结构上修改即可。

具体到静态区间第 k 大，按权值递增的顺序建可持久化区间线段树（树状数组难以可持久化）。
对于每个询问 (l, r, k) 二分答案 x 时只需要在第 x 颗区间线段树上查询 [l, r] 的数的个数。

时间复杂度自然还是 \(O(q logV logn)\) 的，空间复杂度为 \(O(V + n logn)\) 。

同样可以推广到更一般的情况，所有不带修的整体二分实现 2 + 数据结构 A， 都可以用可持久化数据结构 A 做到在线询问。
在可持久没有额外时间开销的前提下，时间复杂度不变，
否则若可持久化会带来 \(O(k)\) 的额外时间复杂度，这样做的时间复杂度同样需要乘上 \(O(k)\) 。
可持久化并查集就是个典型的例子。
同样空间复杂度也要乘上可持久化带来的额外开销。

可惜的是，这不能很好的支持修改，因为每个修改影响到的历史版本是 \(O(V)\) 级别的。

总结

事实上做到在线后，干脆抛弃了整体二分的“整体查询”的思想，其实就和整体二分没什么关系了。
那么整体二分究竟是个什么玩意？
事实上绝大多数整体二分都无法做到比直接数据结构的时间复杂度优秀，
而且经过上述的讨论不难发现绝大多数整体二分都能直接被数据结构替代，
也因此整体二分往往被归在“骗分”，“非正解”一类。

不过整体二分明显的优势在于空间复杂度和实现难度。 不过有时经过整体二分的转换后，就可以使用无法可持久化，或者空间开销大的数据结构，
上面的树状数组就是很好的例子，无论是实现 1 还是实现 2 ，做到在线都必须换成线段树。