Poj 2104 K-th number Solution(划分

#include <cstdio>

#include <cstdlib>

#include <cstring>



using namespace std;



#define MAXN 100001

#define MAXD 100



struct node {

    node *left_child,*right_child;
    int l,r;
    int MID,mid;
    int depth;
    bool flag0;

};



node *roof;

int a[MAXD][MAXN];

int f[MAXD][MAXN];

int n,m;



int get_random(int l,int r){

    int x=0;
    for (int i=0;i++<5;){
        x+=rand();
    }
    x%=(r-l+1);
    x+=l;
    return x;

}





int get_f(int x,node *p){
    if (x<(*p).l){
        return 0;
    }
    return f[(*p).depth][x];

}



//建树

int Build(int l,int r,int depth,node *p){
    (*p).l=l;
    (*p).r=r;
    (*p).depth=depth;
    (*p).flag0=false;
    if (l==r){
        (*p).MID=a[depth][l];
        (*p).mid=l;
        return 0;
    }
    bool flag=true;
    for (int i=l;i++<r;){
        if (a[depth][i]!=a[depth][i-1]){
            flag=false;
            break;
        }
    }
    if (flag){
        (*p).flag0=true;
        (*p).MID=a[depth][l];
        return 0;
    }
    while (1){
        (*p).MID=a[depth][get_random(l,r)];
        (*p).mid=l;
        for (int i=l;i<=r;i++){
            if (a[depth][i]<=(*p).MID){
                a[depth+1][(*p).mid++]=a[depth][i];
                f[depth][i]=get_f(i-1,p)+1;
            } else {
                f[depth][i]=get_f(i-1,p);
            }
        }
        int j=((*p).mid--);
        if ((*p).mid>=r){
            continue;
        }
        for (int i=l;i<=r;i++){
            if (a[depth][i]>(*p).MID){
                a[depth+1][j++]=a[depth][i];
            }
        }
        break;
    }
    Build(l,(*p).mid,depth+1,(*p).left_child=new(node));
    Build((*p).mid+1,r,depth+1,(*p).right_child=new(node));
    return 0;

}



//查询

int find(int l,int r,int k,node *p){
    if ((*p).l==(*p).r||(*p).flag0){
        return (*p).MID;
    }
    if ((*p).flag0){
        return a[(*p).depth][l+k-1];
    }
    int left_s=get_f(r,p)-get_f(l-1,p);
    int right_s=(r-l+1)-left_s;
    int left_=(*p).l+get_f(l-1,p);
    int right_=(*p).mid+(l-(*p).l)-get_f(l-1,p)+1;
    if (k<=left_s) return find(left_,left_+left_s-1,k,(*p).left_child);
    return find(right_,right_+right_s-1,k-left_s,(*p).right_child);

}





int main(){
    srand(0);
    memset(f,sizeof(f),0);
    memset(a,sizeof(a),0);
    scanf("%d%d",&n,&m);
    for (int i=0;i++<n;){
        scanf("%d",&a[0][i]);
    }
    Build(1,n,0,roof=new(node));
    while (m--){
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",find(l,r,k,roof));
    }
    return 0;

}