整体二分
概述:
顾名思义，整体二分是二分答案的一种， 在一些可离线的题目中可以替代一些数据结构， 而且时间一般比数据结构的做法要快.
原论文中提到可以使用整体二分解决的题目需要满足以下性质:
- 询问的答案具有可二分性
- 修改对判定答案的贡献互相独立，修改之间互不影响效果
- 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
- 贡献满足交换律，结合律，具有可加性
- 题目允许使用离线算法 —— 许昊然《浅谈数据结构题几个非经典解法》
实现:
整体二分的思路是: 若对于每个询问二分的过程都基本相同 , 但对每个询问都做一遍二分答案时间无法承受时，可以将所有询问放在一起， 然后做一遍二分即可。这便是” 整体” 的由来.
具体实现上，记 \([l,r]\) 为答案的值域， \([L,R]\) 为修改及询问的处理区间，\([L,R]\) 的修改和询问都只涉及值域 \([l,r]\) 中的数， 同时修改和询问按时间先后排序.
整个算法过程是一个递归:
- 若 \(l=r\), 则 \([L,R]\) 中所有询问答案均为 \(l\).
- 否则设 \(mid = \lfloor (l+r)/2 \rfloor\)(即中间数)
- 按照时间顺序依次处理修改与查询，根据修改数或答案与 \(mid\) 的关系将 \([L,R]\) 分为两个部分， 对这两个部分递归处理.
作用:
整体二分最基本的用途便是求解可离线的动态区间第 K 大 (小).
可以先来思考直接二分该怎么求:
对于二分的一个答案 \(mid\), 计算查询区间 \([ql,qr]\) 中大于 \(mid\) 的数的个数， 如果个数大于等于询问的名次 \(qk\), 则说明答案大于 \(mid\), 否则说明答案小于等于 \(mid\).
然后将所有修改与查询放在一起，对整体进行二分即可。对于修改来讲， 若修改后的数小于等于 \(mid\), 则放在左边的区间，否则放在右边的区间.