概述:
顾名思义, 整体二分是二分答案的一种, 在一些可离线的题目中可以替代一些数据结构, 而且时间一般比数据结构的做法要快.
原论文中提到可以使用整体二分解决的题目需要满足以下性质:
- 询问的答案具有可二分性
- 修改对判定答案的贡献互相独立,修改之间互不影响效果
- 修改如果对判定答案有贡献,则贡献为一确定的与判定标准无关的值
- 贡献满足交换律,结合律,具有可加性
- 题目允许使用离线算法
——许昊然《浅谈数据结构题几个非经典解法》
实现:
整体二分的思路是: 若对于每个询问二分的过程都基本相同, 但对每个询问都做一遍二分答案时间无法承受时, 可以将所有询问放在一起, 然后做一遍二分即可. 这便是”整体”的由来.
具体实现上, 记$[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$, 则放在左边的区间, 否则放在右边的区间.