浅谈整体二分

· · 算法·理论

前言

本人在 oi-wiki 学习整体二分的时候有些坎坷，于是就有了这篇博客。如有什么问题或者没有讲到的点请及时跟我反馈。

前置知识：二分答案

正文

首先我们引入一题。

给定一个长度为 n 的序列，求 [l,r] 区间内的第 k 小。

思路不难想，考虑二分答案。每次二分 \operatorname{check} 是否有 k 个数小于 mid，时间复杂度为 O(n\log n)。

但如果有 q 次询问呢？

那么这个算法的时间复杂度为 O(qn\ logn)。

这就要用到今天的正题——整体二分了。

整体二分的主体思路就是把多个查询一起解决，所以整体二分是一个离线算法。

可以使用整体二分解决的题目需要满足以下性质：

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

2.问题的每次修改操作不会影响其他修改操作的结果，每次修改都是相互独立的。

3.问题的每次修改都会对答案产生一个确定的、与判定标准无关的影响。

4.问题的每次修改操作可以满足交换律、结合律的性质，且多个修改操作对答案的贡献可以进行加和。

5.题目允许使用离线算法。

我们定义一个结构体 qwq(x,y,k,id,type)。对于数组中原来的数，x 表示这个位置的数的大小，id 表示这个位置的数的下标，type 是它的类型（是否被询问）。

对于询问，x,y,k 表示 [x,y] 的区间中查找第 k 小的数，id 表示询问编号。

因为整体二分统计答案时有单点加，区间和的操作，用树状数组维护较为方便。我们考虑用树状数组维护小于 mid 的数，若原序列中的数 ≤mid ，那么树状数组上的对应位置 +1 。将统计和处理询问分开，如果是询问操作，那么查询区间 [x,y] 的值相当于查询了区间中 [l,mid] 的个数，如果个数 ＞k ，则答案在 [l,mid] 中，把操作分到左区间。否则答案就在 [mid+1,r] 中，把 k 减掉对应的个数，把操作分到右区间。

这样查询区间第 k 小的时间复杂度就为 O(n \ log^2 \ V)，其中 V 表示值域。

模板：洛谷 P3834 【模板】可持久化线段树 2

整体二分解法：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e5+5,INF=1e9;
int n,Q,ans[N],a[N],tp,c[N];
struct qwq
{
    int x,y,k,id;
    bool type;
}q1[N<<1],q2[N<<1],q[N<<1];
//树状数组 
inline int lowbit(int x){return x&-x;}
inline void add(int x,int y) 
{
    while(x<=n)
    {
        c[x]+=y;
        x+=lowbit(x);
    } 
}
inline int sum(int x)
{
    int ans=0;
    while(x)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
//主体部分，如上述 
inline void solve(int l,int r,int L,int R)
{
    if(l>r) return;
    if(L==R)
    {
        for(int i=l;i<=r;i++) if(q[i].type) ans[q[i].id]=L;
        return ;
    }
    int mid=(L+R)>>1,cnt1=0,cnt2=0;
    for(int i=l;i<=r;i++)
    {
        if(!q[i].type)
        {
            if(q[i].x<=mid)
            {
                add(q[i].id,1);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        else
        {
            int ans=sum(q[i].y)-sum(q[i].x-1);
            if(ans>=q[i].k) q1[++cnt1]=q[i];
            else{
                q[i].k-=ans;
                q2[++cnt2]=q[i];
            }
        }
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].type) add(q1[i].id,-1);
    for(int i=1;i<=cnt1;i++) q[i+l-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l+cnt1-1]=q2[i];
    solve(l,l+cnt1-1,L,mid);
    solve(l+cnt1,r,mid+1,R);
}
signed main()
{
    cin>>n>>Q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        q[++tp]=(qwq){a[i],1,INF,i,0};
    }
    for(int i=1;i<=Q;i++)
    {
        int l,r,k;
        cin>>l>>r>>k;
        q[++tp]=(qwq){l,r,k,i,1};
    }
    solve(1,tp,-INF,INF);
    for(int i=1;i<=Q;i++) cout<<ans[i]<<endl;;
    return 0;
}

练习题：

洛谷 P1527 [国家集训队] 矩阵乘法

洛谷 P3527 [POI2011] MET-Meteors