整体二分

模板例题

POJ2104 K-th Number

给定一个序列，求其中[l,r]中第k小的数。

 

在一般的做法中，我们暴力枚举[l,r]中的数时，除了得到我们想要的第k小外，还有很多信息，但我们并没有给予一定的重视。
整体二分的全称是“基于值域的整体分治”。
假设值域为[mx,mn]，我们每次枚举一个mid。对于ans小于等于mid的提问（即[vl,mid]中已包含大于等于k个小于等于mid的数），我们放在左边处理，让其在值域范围[vl,mid]中找第k小的数；对于大于mid的（即[vl,mid]中未包含大于等于k个小于等于mid的数），放在右边，让其在值域为[mid+1,vr]中找第k-num(值小于等于mid)小的数。
与此同时，我们把序列中值属于[vl,mid]和[mid+1,vr]分别放到左右两边去，随提问操作。
结束的标志是当区间内没有操作时；或值域唯一时（即[vl,vl]），这时可以得到所有留在这个区间的提问答案均为vl。

具体实现时，不必另开一个数组做“左边”和“右边”，只需要在原序列上稍微调整一下位置就可以了。
对于赋值操作，我们与提问操作一起放入整体二分中，见代码。
对于求区间[li,ri]中小于等于mid的个数，用数组数组来求。对于位置x，如果a[x]<=mid，则add(x,1)。询问区间[l,r]时，有getsum(r)-getsum(l-1)个。
如果不离散化，时间复杂度为。离散后，整体二分区间大大减小，可以降到。
还要注意，对s数组重置时不能打memset，要走原路挨个-1，要不会TLE。
特别注意，给ql、qr计数用的tl、tr一定要写局部变量，全局变量有大问题！

 

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5+10,maxm=5010;

int n,m;
int taa,a[maxn];
struct U{int opt,x,y,z;}q[maxn+maxm];int len=0;//opt=0表示赋值；opt>0表示操作编号 

int s[maxn];
void add(int x,int c)
{
    for(;x<=n;x+=x&-x) s[x]+=c;
}
int getsum(int x)
{
    int re=0;
    for(;x>=1;x-=x&-x) re+=s[x];
    return re;
}

int ans[maxm];
U ql[maxn],qr[maxn];
void solve(int vl,int vr,int st,int ed)//在离散值[vl,vr]中解决q[st~ed]的操作 
{
    if(st>ed) return ;//q为空 
    if(vl==vr)//有答案了 
    {
        for(int i=st;i<=ed;i++)
            if(q[i].opt>0) ans[q[i].opt]=vl;
        return ;
    }
    
    int tl=0,tr=0;//这里定义局部变量 
    int mid=vl+vr>>1;
    for(int i=st;i<=ed;i++)
        if(q[i].opt==0)
        {
            if(q[i].y<=mid) add(q[i].x,1),ql[++tl]=q[i];
            else qr[++tr]=q[i];
        }
        else
        {
            int k=getsum(q[i].y)-getsum(q[i].x-1);//区间内小于等于mid的数有多少个 
            if(q[i].z<=k) ql[++tl]=q[i];
            else q[i].z-=k,qr[++tr]=q[i];//记得q[i].z-=k！ 
        }
    for(int i=st;i<=ed;i++)//还原 
        if(q[i].opt==0 && q[i].y<=mid) add(q[i].x,-1);
    
    for(int i=st,j=1;j<=tl;i++,j++) q[i]=ql[j];
    for(int i=st+tl,j=1;j<=tr;i++,j++) q[i]=qr[j];
    solve(vl,mid,st,st+tl-1);
    solve(mid+1,vr,st+tl,ed);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        len++;
        q[len].opt=0;q[len].x=i;
        scanf("%d",&q[len].y);a[i]=q[len].y;
    }
    sort(a+1,a+n+1);
    taa=unique(a+1,a+n+1)-(a+1);
    for(int i=1;i<=len;i++)
    {
        q[i].y=lower_bound(a+1,a+taa+1,q[i].y)-a;
    }
    for(int i=1;i<=m;i++)
    {
        len++;
        q[len].opt=i;
        scanf("%d%d%d",&q[len].x,&q[len].y,&q[len].z);
    }
    solve(1,taa,1,len);
    for(int i=1;i<=m;i++) printf("%d\n",a[ans[i]]);//离散值还原原值 
    return 0;
}