hdu 2665 （poj 2104） 劃分樹

poj2104題目要求弱一些，n個數是不同的。hdu2665中沒有這樣的限制。所以在劃分左右區間時需要處理一下相同的數怎麼劃分。

[cpp] 
#include<stdio.h> 
#include<algorithm> 
#include<string.h> 
#define M 100010 
using namespace std; 
 
int tr[20][M],num[20][M],sorted[M]; 
 
void build(int l,int r,int d) 
{ 
    if(l==r) return ; 
    int m=(l+r)/2; 
    int lp=l,rp=m+1; 
    int h=1; 
    for(int j=m-1;j>=l;j--) 
    { 
        if( sorted[j]==sorted[m] ) 
            h++; 
        else break; 
    } 
    for(int i=l;i<=r;i++) 
    { 
        num[d][i]=num[d][i-1]; 
 
        if( tr[d][i]<sorted[m]  && lp<=m) 
        { 
            tr[d+1][lp++]=tr[d][i]; 
            num[d][i]++; 
        } 
        else 
            if( tr[d][i]==sorted[m]) 
            { 
                if( h>0 ) {  tr[d+1][lp++]=tr[d][i],h--; num[d][i]++; } 
                else tr[d+1][rp++]=tr[d][i]; 
            } 
            else 
            { 
                tr[d+1][rp++]=tr[d][i]; 
            } 
    } 
    build(l,m,d+1); 
    build(m+1,r,d+1); 
} 
 
int query(int s,int t,int k,int l,int r,int d) 
{ 
    int m=(l+r)/2; 
    if(s==t) return tr[d][s]; 
 
    int p=num[d][t]-num[d][s-1]; 
    int sl=num[d][s-1]-num[d][l-1]; 
 
    if( p>=k ) 
    { 
        return query(l+sl,l+sl+p-1,k,l,m,d+1); 
    } 
    else 
    { 
        int b=s-l-sl; int bb=t-s+1-p; 
        return query( m+b+1,m+b+bb,k-p,m+1,r,d+1); 
    } 
} 
 
int main() 
{ 
    int n,m,i,j,k,s,t,T; 
    scanf("%d",&T); 
    while(T--){ 
        scanf("%d%d",&n,&m); 
        memset(num,0,sizeof(num)); 
        memset(tr,0,sizeof(tr)); 
        for(i=1;i<=n;i++) 
        { 
            scanf("%d",&sorted[i]); 
            tr[0][i]=sorted[i]; 
        } 
        sort(sorted+1,sorted+n+1); 
        build(1,n,0); 
        for(i=1;i<=m;i++) 
        { 
            scanf("%d%d%d",&s,&t,&k); 
            int ans=query(s,t,k,1,n,0); 
            printf("%d\n",ans); 
        } 
    } 
    return 0; 
}