求Kth number的算法

把百度博客的帖子转过来，扩充一下门面吧~~

试着交o（n）的模板，基于快排，tle，估计是查询太多的原因吧，最后只得xiaoxi下递归树＋二分的方法，

看得明白些，敲代码熟悉下，思想是利用归并排序的递归给一个附带的数组sortseq［level］［i］排序，

样子如下

level 0) [1,  2,  3,  4,  5,  6,  7,  inf]

level 1) [1,  2,  5,  6] [3,  4,  7,  inf]

level 2) [1,  5] [2,  6] [3,  7] [4,  inf]

level 3) [1] [5] [2] [6] [3] [7] [4] [inf]

同时还生成一个线段树，每个节点域内存放左儿子和右儿子。

然后对每次查询s，t，k，用二分法生成一个val搜索树中表示的区间［tree［p］.l,tree[p].r］ 

属于 ［s，t］的，然后判读几个小于比val小的数有几个，得出val排第几个，如果其排名小于或者大

于k，则继续二分，直到发现val排名恰好是k时结束，

代码如下：

#include<iostream>

#include<algorithm>

using namespace std;

#define maxn 100010

int n,m;

int S,T,K;

int seq[maxn],sortseq[25][maxn];

int depth;

struct Tree{

       int l,r;

}tree[maxn*3];

void setTree(int p,int l,int r,int depth)

{

       tree[p].l=l;tree[p].r=r;

       if(l==r){

              sortseq[depth][l]=seq[l];

              return ;

       }

       int mid=(l+r)>>1;

       setTree(p*2,l,mid,depth+1);

       setTree(p*2+1,mid+1,r,depth+1);

       int i,j,k;

       k=i=l;j=mid+1;

       while(i<=mid &&j<=r){

              if(sortseq[depth+1][i]<sortseq[depth+1][j])

                     sortseq[depth][k++]=sortseq[depth+1][i++];

              else sortseq[depth][k++]=sortseq[depth+1][j++];

       }
       
       while(i<=mid)
  
  sortseq[depth][k++]=sortseq[depth+1][i++];
       
       while(j<=r)
  
  
  sortseq[depth][k++]=sortseq[depth+1][j++];
       
}

int query(int p,int val,int depth)
  
{//printf("come into query(%d , %d , %d) and zuoerzi %d , youerzi %d\n",p,val,depth,tree[p].l,tree[p].r);

  
  if(S<=tree[p].l && tree[p].r<=T)
    
                                                                              //对有序数列二分查找，返回地址

    
    // {cout<<"comehrer"<
    // cout<<"return is "<
return lower_bound(&sortseq[depth][tree[p].l], &sortseq[depth][tree[p].r]+1,val)-&sortseq[depth][tree[p].l];
  //}

  
  int res=0;
  
  if(S<=tree[p*2].r)
    
    res+=query(p*2,val,depth+1);
  
  if(T>=tree[p*2+1].l)
    
    res+=query(p*2+1,val,depth+1);
  // cout<<"res fanhui"<
       return res;
       
}

int main()

{

       int i,l,r,mid,key,kk;

       while(scanf("%d%d",&n,&m)==2)

       {

              for(i=1;i<=n;i++)

                     scanf("%d",&seq[i]);

              setTree(1,1,n,1);
       for(int i=1;i<=5;++i){for(int j=0;j<=10;++j)cout<<sortseq[i][j]<<' ';cout<<endl;}

              while(m--){

                     scanf("%d%d%d",&S,&T,&K);

                     K--;

                     l=1;r=n;

                     while(l<=r){

                            mid=(l+r)>>1;

                            kk=query(1,sortseq[1][mid],1);

                            if(kk<=K){

                                   key=mid;

                                   l=mid+1;

                            }

                            else

                                   r=mid-1;

                     }

                     printf("%d\n",sortseq[1][key]);

              }

       }

       return 0;

}