区间k小数(1)

Posted on By 二价氢

在线段树的学习当中,我们会了解到线段树的应用之一就是求区间极值Range Maxinum/Minium Query,比如区间最大值,区间最小值等等。这一类值都有一个性质就是满足区间加法的性质,即两个区间的区间最大值等于两个区间各自的最大值中较大的一个,但是,如果是求区间k小数Range K-th number的话,就不能用简单的区间加法实现。

但是,我们注意到,在归并排序的过程中,我们其实实现了类似于区间加法的区间合并的操作,因而,我们可以在归并排序的过程中建线段树Segment Tree,用表示递归第层中第位的数字。

同时用表示在归并第层中位置的左侧数字数量(即,比它小的数字数量)

然后,在询问Query过程中我们二分即可。

例题:POJ 2104 K-th Number(这明明是OI题好么?)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> II;
int n,m,s[30][100005],a[30][100005];
II b[100005];
void build(int dep,int l,int r)
{
    if (l==r)
        return;
    int mid=(l+r)/2;
    int cl=0,L=l-1,R=mid;
    for (int i=l;i<=r;i++)
    {
        if (L<=mid&&a[dep-1][i]<=b[mid].first)
        {
            a[dep][++L]=a[dep-1][i];
            s[dep][i]=++cl;
        }else
        {
            a[dep][++R]=a[dep-1][i];
            s[dep][i]=cl;
        }
    }
    build(dep+1,l,mid);
    build(dep+1,mid+1,r);
}
int query(int dep,int S,int T,int l,int r,int k)
{
    if (l==r)
        return a[dep-1][l];
    int mid,L,R;
    mid=(S+T)/2;
    L=(l==S)?0:s[dep][l-1];
    R=s[dep][r];
    if (R-L>=k)
        return query(dep+1,S,mid,S+L,S+R-1,k);
    else
        return query(dep+1,mid+1,T,mid+1+l-S-L,mid+1+r-S-R,k-R+L);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&b[i].first);
        b[i].second=i;
        a[0][i]=b[i].first;
    }
    sort(&b[1],&b[n+1]);
    build(1,1,n);
    int l,r,k;
    while (m--)
    {
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",query(1,1,n,l,r,k));
    }
    return 0;
}