一直想做的【区间内第k大数】终于完成了。

spoj上rank11.poj上rank10086- -。

最近才知道在前段时间yy出来的那个东西叫划分树。能且仅能解决不带修改的【区间内第k大数】。N个数Q个询问，则空间复杂度O(nlogn)，时间复杂度O(nlogn+qlogn)。

代码64行- -写了好久。【显示出来才觉得自己的代码和翔真是相近。一直只是对别人的代码这么感觉的- -】

#define NN 101001
#define LOG 21
#include <cstdio>
#include <algorithm>
struct inf{int val,from;}rank[NN];
bool cmp(const inf& t1,const inf& t2){return t1.val<t2.val;}
int n,a[NN],b[NN],f[LOG][NN],h;
void swap(int i1,int i2){int tmp=a[i1];a[i1]=a[i2];a[i2]=tmp;}
void build(int l,int r,int cs)
{
    if(l==r)return;
    if(cs>h)h=cs;
    int mid=(l+r)>>1,c=0,d=0;
    if(a[l]<=mid){c=1;f[cs][l]=1;}else{f[cs][l]=0;d=1;b[1]=a[l];}
    for(int i=l+1;i<=r;i++)
    {
        if(a[i]<=mid)
        {
            ++c;
            swap(l+c-1,i);
            f[cs][i]=f[cs][i-1]+1;
        }
        else
        {
            f[cs][i]=f[cs][i-1];
            b[++d]=a[i];
        }
    }
    for(int i=mid+1;i<=r;i++)a[i]=b[i-mid];
    build(l,mid,cs+1);
    build(mid+1,r,cs+1);
}
int query(int l,int r,int k,int cs,int ll,int rr)
{
    if(ll==rr&&k==1)return rank[ll].val;
    int mid=(ll+rr)>>1,count=f[cs][r]-f[cs][l],start=f[cs][l]+1,end;
    if((ll==l&&f[cs][l]==1)||(l>ll&&f[cs][l]>f[cs][l-1])){++count;start=f[cs][l];}
    if(count>=k)
        return query(ll+start-1,ll+f[cs][r]-1,k,cs+1,ll,mid);
    else
    {
        start=(l-ll+1)-f[cs][l];
        if((ll==l&&f[cs][l]==1)||(l>ll&&f[cs][l]>f[cs][l-1]))++start;
        end=(r-ll+1)-f[cs][r];
        return query(mid+start,mid+end,k-count,cs+1,mid+1,rr);
    }
}
int main()
{
    int q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);rank[i].val=a[i];rank[i].from=i;}
    std::sort(rank+1,rank+n+1,cmp);
    for(int i=1;i<=n;i++)a[rank[i].from]=i;
    build(1,n,1);
    int l,r,k;
    for(int i=1;i<=q;i++)
    {
        scanf("%d %d %d",&l,&r,&k);
        printf("%d\n",query(l,r,k,1,1,n));
    }
}

写的第一个比较奇葩的数据结构。写完了肾是欣慰- -

累死我了- -。

划分树详细说明 http://seter.is-programmer.com/posts/30030.html