整体二分（二分进阶）

前言：

Claris表示：这东西考试的时候估计是用不上的，现在很多题目，尤其是高级数据结构题都会强制在线

但是今天挖的坑，不知道什么时候就会掉进去。。。早填早安心

知识储备

二分答案——整体二分的前世

首先对于一类查询而言，我们要找的答案满足二分性：

例如：区间第K大

这时候我们就可以采用二分答案的方法来解决，二分答案是把九三问题转化为判定问题的有效手段

二分答案的做法是不断维护一个可能的答案区间[L,R]，每次二分，我们先求出当前的判定答案

M=(L+R)>>1，然后我们统计在当前标准下会对查询产生贡献的修改（例如参数<=M）的贡献和，

我们再比较现在的贡献和与我们想要的贡献和的大小，如果贡献已经超过我们想要的贡献和，说明符合标准的修改太多了，我们需要缩紧标准 —>[L,M]

否则我们就要放宽标准 —>[M+1,R]

算法介绍

整体二分，就像题目说的那样：是朴素二分的进阶版

整体思路有一点像CDQ分治

看一下《浅谈数据结构题的几个非经典解法》中的介绍：

所谓整体二分，需要数据结构题满足以下性质：

1. 询问的答案具有可二分性

2. 修改对判定答案的贡献相对独立，修改之间互不影响效果

3. 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值

4. 贡献满足交换律，结合律，具有可加性

5. 题目允许离线操作

询问的答案有可二分性质显然是前提，我们发现，因为修改对判定标准的贡献相对独立，且贡献的值（如果有的话）与判定标准无关，所以如果我们已经计算过某一些修改对询问的贡献，那么这个贡献永远不会改变，我们没有必要当判定标准改变时再次计算这部分修改的贡献，只要记录下当前的总贡献，再进一步二分时，直接加上新的贡献即可

这样的话，我们发现，处理的复杂度可以不再与序列总长度直接相关了，而可能只与当前待处理序列的长度相关

我仔细一琢磨，这不就是CDQ嘛。。。

实际上说不同也是有不同的（不同点还不少）

具体流程

我们先看一道例题：带修改区间第k小数

一看，哎呦，这不是主席树嘛？

但是我们就是要没事找事

对于单个查询而言，我们可以采用预处理+二分答案的方法解决，但现在我们要回答的是一系列的查询，对于查询而言我们都要重新预处理然后二分，时间复杂度无法承受，但是我们仍然希望通过二分答案的思想来解决，整体二分就是基于这样一种想法——我们将所有操作（包括修改和查询）一起二分，进行分治

整体二分具体做法比较难理解，看一下伪代码：

Divede(Q,L,R)
//Q是当前处理的操作序列 
//WANT是要求的贡献,CNT为已经累计的贡献(记录的是1~L-1所有修改的贡献) 
//[L,R]是询问的答案范围区间
if L=R then
    将Q中所有是询问操作的答案设为L
end if 
//我们二分答案,M是当前的判定答案
M=(L+R)>>
//solve是主处理函数,只考虑参数满足判定标准[L,R]的修改的贡献,
//因为CNT域中已经记录了[1,L-1]的修改的贡献了,这一步是保证时间复杂度的关键,
//solve只与当前Q的长度有关,而不与整个操作序列的长度有线性关系 
solve(Q,L,M);
//solve之后Q中各个参数满足判定标准的修改对询问的贡献被储存在ANS数组 
//Q1,Q2为了两个临时数组,由于划分操作序列
for i= to Length(Q) do
    if (Q[i].WANT<=Q[i].CNT+ANS[i]) then
        //当前已有贡献不小于要求贡献，说明最终答案应当不大于判定答案 
        向数组Q1末尾添加Q[i] 
    else
        //当前已有贡献小于要求贡献,说明最终答案应当大于判定答案 
        //这里是整体二分的关键,把当前贡献累计入总贡献,以后不再重复统计 
        Q[i].CNT=Q[i].CNT+ANS[i]
        向数组Q2末尾添加Q[i]
    end if
end for
//分治,递归处理 
Divide(Q1,L,M)
Divede(Q2,M+,R) 
           

我们时刻维护一个操作序列和对应的可能答案区间[L,R]

我们先求的一个判定答案M=（L+R）>>1

然后我们考虑操作序列的修改操作，将其中符合条件（例如参数<=M）的修改对各个询问的贡献统计出来

然后我们对操作序列进行划分

• 第一类操作是查询

  • 如果当前累计贡献比要求贡献大，说明M过大，满足标准的修改过多，我们需要给这个查询设置更小的答案区间，于是把ta划分到答案区间[L,M]

    （这种情况下我们不改变查询的CNT域，保证了继续下一次分治时这些查询的CNT还是累计[1,L-1]的修改的贡献）

  • 否则我们将当前已经统计到的贡献更新，将ta划分到[M+1,R]

    （这种情况下我们将[L,M]内的修改的贡献更新了CNT域，保证了下次继续分治时这些查询的CNT域已经保留的是[1，M]的贡献了）

• 第二类操作是修改

  假如ta符合当前的标准，已经被统计入了贡献，那么ta对于答案区间是[M+1，R]的查询来说已经没有意义

  （因为我们知道ta一定会对这些查询产生贡献，并且我们已经累计了这种贡献到CNT域中），我们就把ta划分到[L,R]的区间里

  对于不符合当前的标准，未被统计入贡献的修改来说，如果我们放宽标准，ta有可能起贡献，然而我们并未统计这种贡献，因此对于[M+1,R]的区间来说它仍具有考虑的意义，我们把它划分到[M+1,R]中

划分好了操作之后，我们就可以继续二分下去了

时间复杂度

和CDQ分治一样，整体二分的复杂度也是O(f(n)logn)

说了这么多，还是看例题：poj2104 K-th Number

题解