天天看点

整体二分(二分进阶)

前言:

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

题解