[HDOJ2665 Kth number]【划分树】【例题】

【题目大意】给定一个数列。多个询问，问区间中第k小的数是哪个。

【算法分析】

既然是例题系列，那么讲一下划分树。

大体上是采用分治思想。每次取一中位数划分为左右两边。然后在同一区间内，数的顺序与在原数组中的顺序一样。

建立的话。我们可以通过自底向上的归并来达到lg n的建立。

然后询问时，通过To_L[]表示这个区间内，前i个数字有多少个被划分去了左边，可以快速判断。达到lg n的效果。

【其它】

这个英语太强大了。kth big number

【CODE】

#include

#include #include #include #include using namespace std;
const int N=105555;
int Tc,n,m,spt;
int a[N],b[N*20],To_L[N*20];
struct Node{int l,r,St,Ed;}Tr[N*5];
bool cmp(int i,int j){return a[i]     scanf("%d%d",&n,&m);
     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
     for (int i=1;i<=n;i++) b[i]=i;
     sort(b+1,b+n+1,cmp);
     spt=n;
}

void Union(int p,int s1,int e1,int s2,int e2){
     Tr[p].St=spt+1;
     int i=s1,j=s2,Sum=0;
     while (i<=e1 || j<=e2){
       if (i<=e1 && (j>e2 || b[i]                                    else b[++spt]=b[j++];
       To_L[spt]=Sum;
     }
     Tr[p].Ed=spt;
}

void build(int p,int l,int r){
     Tr[p].l=l; Tr[p].r=r;
     if (l==r){
       Tr[p].St=Tr[p].Ed=l;
       return;
     }
     int mid=(l+r)/2,i;
     build(p*2,l,mid);
     build(p*2+1,mid+1,r);
     Union(p,Tr[p*2].St,Tr[p*2].Ed,Tr[p*2+1].St,Tr[p*2+1].Ed);
}

int Query(int p,int l,int r,int k){
    if (Tr[p].l==Tr[p].r) return a[b[Tr[p].St]];
    int LL=0,RR,res;
    RR=To_L[Tr[p].St+r-1];
    if (l!=1) LL=To_L[Tr[p].St+l-2];
    res=RR-LL;
    if (res>=k) return Query(p*2, LL+1 , LL+res ,k);
    else{
      k-=res;
      res=r-l+1-res;
      if (l!=1) LL=l-1-LL;
      return Query(p*2+1,LL+1,LL+res,k);
    }
}

void solve(){
     int l,r,k,i;
     for (i=0;i         scanf("%d%d%d",&l,&r,&k);
         printf("%dn",Query(1,l,r,k));
     }
}

int main(){
    scanf("%d",&Tc);
    for (int i=0;i        init();
        build(1,1,n);
        solve();
    }
    return 0;
}