整体二分学习笔记

lizhous · 2023-06-05 18:16:08 · 个人记录

概念

对于一个很多询问的题，假如对于一个询问可以二分处理，同时一次 check 可以只用 n 的时间处理所有询问的 check 结果，我们可以使用整体二分来做这个题。

思想

设函数 \operatorname{solve}(S, L, R) 为现在正在处理询问序列 S 里的询问，答案值域为 [L, R]。

向下递归直到 L=R，即求出了答案。

否则对于 mid 执行 check，比较并将 S 分成两部分向下递归 [l,mid]，[mid+1,r]。

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,a[1000001],lsh[1000001],ans[1000001];
struct qw
{
    int op,l,r,k,i;
}q[1000001],lt[1000001],rt[1000001];
int snmn[1000001];
void add(int x,int w)
{
    while(x<=n)
    {
        snmn[x]+=w; 
        x+=(x&(-x));
    }
}
int sum(int x)
{
    int re=0;
    while(x)
    {
        re+=snmn[x];
        x-=(x&(-x));
    }
    return re;
}
void tp(int l,int r,int L,int R) //l-r询问 L-R答案
{
    int ll=0,rl=0;
    if(l>r) return;
    if(L==R)
    {
        for(int i=l;i<=r;i++)
        {
            if(q[i].op==1) continue;
            ans[q[i].i]=L; 
        }
        return;
    }
    int mid=L+R>>1;
    for(int i=l;i<=r;i++)
    {
        if(q[i].op==1)
        {
            if(q[i].r<=mid)
            {
                add(q[i].k,1);
                lt[++ll]=q[i];
            }
            else
            {
                rt[++rl]=q[i];
            }
        }
        else
        {
            int cnt=sum(q[i].r)-sum(q[i].l-1);
            if(q[i].k<=cnt)
            {
                lt[++ll]=q[i];
            }
            else
            {
                q[i].k-=cnt;
                rt[++rl]=q[i];
            }
        }
    }
    for(int i=l;i<=r;i++)
    {
        if(q[i].op==1&&q[i].r<=mid) add(q[i].k,-1);
    }
    for(int i=1;i<=ll;i++)
    {
        q[l+i-1]=lt[i];
    }
    for(int i=1;i<=rl;i++)
    {
        q[l+ll+i-1]=rt[i];
    }
    tp(l,l+ll-1,L,mid);
    tp(l+ll,r,mid+1,R);
}
signed main()
{
    scanf("%d%d",&n,&m);
    m+=n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        lsh[i]=a[i];
    }
    sort(lsh+1,lsh+n+1);
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(lsh+1,lsh+n+1,a[i])-lsh;
    }
    for(int i=1;i<=n;i++)
    {
        q[i].r=a[i];
        q[i].k=i;
        q[i].op=1;
    }
    for(int i=n+1;i<=m;i++)
    {
        q[i].op=2;
        scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);
        q[i].i=i-n;
    }
    tp(1,m,1,n);
    for(int i=1;i<=m-n;i++)
    {
        printf("%d\n",lsh[ans[i]]);
    }
}