djwj233 的博客

djwj233 的博客

整体二分 学习笔记

posted on 2021-09-09 20:23:08 | under 笔记 |

Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

Binary search 大法好!!1

什么是整体二分

一种基于值域的整体分治算法,是离线做法

核心思想是二分答案、重复利用信息

整体二分的主过程

以上是板子题,大意为:给定数列 $a_{1\cdots n}$,多次询问某段区间第 $k$ 小的数。

这题是经典题,有很多种解法,这里我们使用整体二分。

  1. 先考虑二分答案之后对单个询问怎么处理。

    我们可以想到二分一个答案 $mid$,然后询问便转化为多次询问一段区间内不小于 $mid$ 的数有几个

    这可以轻松地用 BIT 进行维护。

  2. 处理后,我们把处理的询问分为两部分:

    • 答案不大于 $mid$ 的;
    • 答案大于 $mid$ 的;

    然后对二者分别递归处理。

  3. 需要注意的是,我们一般会把整体二分中数列的信息直接表示成一次赋值操作,然后与询问一同处理。

  4. 最后清空 BIT。不过我们只能一个一个地把加上的数减回来,否则复杂度是错的。

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v=a;v<=b;v++)
#define fr(v,a,b) for(int v=a;v>=b;v--)
#define il inline

const int N=100010,M=200010;

int n,m,a[N];
int inp[N],tot;

struct query {
    int opt,id;
    int l,r,k;
} q[M],lq[M],rq[M];
int ans[N];

int b[N];
void add(int x,int c) {
    for(;x<=n;x+=x&-x)
        b[x]+=c;
}
int ask(int x) {
    int res=0;
    for(;x;x-=x&-x)
        res+=b[x];
    return res;
}
void solve(int lv,int rv,int l,int r)
{
    if(lv==rv) {
        fo(i,l,r) if(q[i].opt==1)
            ans[q[i].id]=lv;
        return ;
    }
    if(lv>rv||l>r) return ;

    int mid=(lv+rv)>>1,p1=0,p2=0;
    fo(i,l,r)
    {
        if(q[i].opt==0) {
            if(q[i].k>mid) rq[++p2]=q[i];
            else {
                lq[++p1]=q[i], add(q[i].l,1);
            }
        } else {
            int cur=ask(q[i].r)-ask(q[i].l-1);
            if(cur>=q[i].k) lq[++p1]=q[i];
            else rq[++p2]=q[i], rq[p2].k-=cur;
        }
    }

    fo(i,1,p1) {
        q[i+l-1]=lq[i];
        if(lq[i].opt==0) add(lq[i].l,-1);
    }
    fo(i,1,p2) q[i+l+p1-1]=rq[i];
    solve(lv,mid,l,l+p1-1), solve(mid+1,rv,l+p1,r);
}

int main()
{
    cin>>n>>m;
    fo(i,1,n) scanf("%d",&a[i]),inp[i]=a[i];

    sort(inp+1,inp+n+1);
    tot=unique(inp+1,inp+n+1)-(inp+1);
    fo(i,1,n) a[i]=lower_bound(inp+1,inp+n+1,a[i])-inp;

    fo(i,1,n) q[i].opt=0, q[i].l=i, q[i].k=a[i];
    fo(i,1,m) {
        q[i+n].opt=1, q[i+n].id=i;
        scanf("%d%d%d",&q[i+n].l,&q[i+n].r,&q[i+n].k);
    }

    solve(1,tot,1,n+m);
    fo(i,1,m) printf("%d\n",inp[ans[i]]);

    return 0;
}

这个问题还可以支持单点修改,做法是直接把修改插入到询问中去。

由于整体二分过程中不改变操作的先后顺序,因此这个做法是正确的。

时间复杂度 $\Theta(n\log^2 n)$。

一般来说,求第 $k$ 大的数都可以考虑整体二分

整体二分的基础应用

整体二分最主要的特点:

  • 可以通过二分答案解决;
  • 需要回答多个询问;
  • 离线。

具体可以通过以下几道例题进行分析,思维难度大致不超过提高组。

所谓的「H 指数」自然想到可以用二分来求,于是整体二分。

思路较为自然。Code

看到询问 K 大值,可以考虑使用整体二分。

这里相当于要在整体二分的基础上多一个区间加区间和,维护一棵线段树即可。

Code

可以在原来的基础上改成一个二维的树状数组。

Code

在带修整体二分上加一个树剖。代码没写。

整体二分进阶