整体二分学习笔记

整体二分一般适用于解决可以若干次二分解决的问题，当进行若干次二分的复杂度无法接受时，就可以使用整体二分。

可以使用整体二分解决的题目需要满足以下性质：
1.询问的答案具有可二分性
2.修改对判定答案的贡献互相独立，修改之间互不影响效果
3.修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
4.贡献满足交换律，结合律，具有可加性
5.题目允许使用离线算法
——许昊然《浅谈数据结构题几个非经典解法》

P3834 【模板】可持久化线段树 2

以静态区间第 \(k\) 小，讲解一下算法流程。

首先将所有询问离线，然后对答案的值域 \([1,Max_{val}]\) 进行分治（二分），设当前值域为 \([L,R]\)，考虑对于一个区间 \([x,y]\) 查询第 \(k\) 小，若保证其答案在 \([L,R]\) 之间，但是 \([L,R]\) 之间小于 \(mid\) 的数的个数小于 \(k\)，那么就说明此询问答案一定在 \([mid+1,R]\) 之间，显然这样可以根据一个 \(mid\) 值将所有询问分为两部分，将两部分的询问分别下传到 \([L,mid]\) 和 \([mid+1,R]\) 伤，我们递归不断重复此过程，直到值域 \(L=R\)，此时该区间上挂着的询问答案即为 \(L\)。

如何查询\([L,R]\) 之间小于 \(mid\) 的数的个数？使用树状数组，每次将所有小于 \(mid\) 的数插入树状数组，查询前缀和做差即可。

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

P2617 Dynamic Rankings

动态区间第 \(k\) 小。

考虑将一次修改变为在原位置上减去原来的数，再加上一个新数，离线时将原有的数也视作加一个新数，将加减操作和查询操作离线到同一个数组里，整体二分时按照操作顺序边修改树状数组b边查询，这就保证的操作的时序性。其他同静态版本。