划分树

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
int cmp(const void *a,const void *b) {return *(int *)a-*(int *)b;}
const int size=100001;

int a[size],sh[18][size],hf[18][size];//记得要多算一层哦
void build(int dep,int l,int r)
{
    if (l==r) return;
    int mid=l+r>>1,ll=l,rr=mid+1;
    int s=0; FOR(i,l,mid) if (a[i]==a[mid]) ++s;
    FOR(i,l,r)
    {
        if (sh[dep][i]>a[mid] || (sh[dep][i]==a[mid]&&!s))
            sh[dep+1][rr++]=sh[dep][i],hf[dep][i]=hf[dep][i-1];
        else
            sh[dep+1][ll++]=sh[dep][i],hf[dep][i]=hf[dep][i-1]+1;
        if (sh[dep][i]==a[mid]) --s;
    }
    build(dep+1,l,mid); build(dep+1,mid+1,r);
}
int red(int n,int ll,int rr,int k)
{
    int l=1,r=n,mid=l+r>>1,dep=0;
    int ls,n2;
    for (;l<r;dep++,mid=l+r>>1)
    {
        ls=hf[dep][rr]-hf[dep][ll-1]; n2=hf[dep][rr]-hf[dep][l-1];
        if (k<=ls) ll=l+n2-ls,rr=l+n2-1,r=mid;
        else k=k-ls,ll=mid+(ll-l+1)+ls-n2,rr=mid+(rr-l+1)-n2,l=mid+1;
    }
    return a[l];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d",a+i),sh[0][i]=a[i];
    qsort(&a[1],n,sizeof(a[1]),cmp);
    build(0,1,n);
    int x,y,z;
    rep(o,m)
    {
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",red(n,x,y,z));
    }
    return 0;
}

}}}

#include <cstdio>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define FOR(i,l,r) for (int i=(l);i<=(r);i++)
int cmp(const void *a,const void *b) {return *(int *)a-*(int *)b;}
const int size=100001;
int a[size],sh[18][size],hf[18][size];//记得要多算一层哦
void build(int dep,int l,int r)
{
    if (l==r) return;
    int mid=l+r>>1,ll=l,rr=mid+1;
    int s=0; FOR(i,l,mid) if (a[i]==a[mid]) ++s;
    FOR(i,l,r)
    {
        if (sh[dep][i]>a[mid] || (sh[dep][i]==a[mid]&&!s))
            sh[dep+1][rr++]=sh[dep][i],hf[dep][i]=hf[dep][i-1];
        else
            sh[dep+1][ll++]=sh[dep][i],hf[dep][i]=hf[dep][i-1]+1;
        if (sh[dep][i]==a[mid]) --s;
    }
    build(dep+1,l,mid); build(dep+1,mid+1,r);
}
int red(int n,int ll,int rr,int k)
{
    int l=1,r=n,mid=l+r>>1,dep=0;
    int ls,n2;
    for (;l<r;dep++,mid=l+r>>1)
    {
        ls=hf[dep][rr]-hf[dep][ll-1]; n2=hf[dep][rr]-hf[dep][l-1];
        if (k<=ls) ll=l+n2-ls,rr=l+n2-1,r=mid;
        else k=k-ls,ll=mid+(ll-l+1)+ls-n2,rr=mid+(rr-l+1)-n2,l=mid+1;
    }
    return a[l];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    FOR(i,1,n) scanf("%d",a+i),sh[0][i]=a[i];
    qsort(&a[1],n,sizeof(a[1]),cmp);
    build(0,1,n);
    int x,y,z;
    rep(o,m)
    {
        scanf("%d%d%d",&x,&y,&z);
        printf("%d\n",red(n,x,y,z));
    }
    return 0;
}