整体二分



概述:

顾名思义, 整体二分是二分答案的一种, 在一些可离线的题目中可以替代一些数据结构, 而且时间一般比数据结构的做法要快.

原论文中提到可以使用整体二分解决的题目需要满足以下性质:

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

实现:

整体二分的思路是: 若对于每个询问二分的过程都基本相同, 但对每个询问都做一遍二分答案时间无法承受时, 可以将所有询问放在一起, 然后做一遍二分即可. 这便是”整体”的由来.

具体实现上, 记$[l,r]$为答案的值域, $[L,R]$为修改及询问的处理区间, $[L,R]$的修改和询问都只涉及值域$[l,r]$中的数, 同时修改和询问按时间先后排序.

整个算法过程是一个递归:

  1. 若$l=r$, 则$[L,R]$中所有询问答案均为$l$.
  2. 否则设$mid = \lfloor (l+r)/2 \rfloor$(即中间数)
  3. 按照时间顺序依次处理修改与查询, 根据修改数或答案与$mid$的关系将$[L,R]$分为两个部分, 对这两个部分递归处理.

作用:

整体二分最基本的用途便是求解可离线的动态区间第K大(小).

可以先来思考直接二分该怎么求:

对于二分的一个答案$mid$, 计算查询区间$[ql,qr]$中大于$mid$的数的个数, 如果个数大于等于询问的名次$qk$, 则说明答案大于$mid$, 否则说明答案小于等于$mid$.

然后将所有修改与查询放在一起, 对整体进行二分即可. 对于修改来讲, 若修改后的数小于等于$mid$, 则放在左边的区间, 否则放在右边的区间.

题解链接