poj 2104 (求区间第K大元素)

[cpp]
//为了做一道题，以前不知道什么划分树，只能从最基本的学，这是入门题，看了别人了代码，然后慢慢写的
[cpp]
#include <iostream>
using namespace std ;
const int MAXN = 100010 ;
int data[30][MAXN], sorted[MAXN], toleft[30][MAXN] ;
int cmp(const void *a, const void *b){
    return *(int *)a < *(int *)b ? -1 : 1 ;
}
void build(int l, int r, int d){
    if(l==r)    return ;
    int i ;
    int m = (l + r) >> 1 ;
    int ls = m - l + 1 ;   //用来标记和中间值m相等的，且分到左孩子的数的个数。
                           //初始时，假定当前区间[l,r]有mid-l+1个和m 相等。
                           //先踢掉比中间值小的,剩下的就是要插入到左边的*/
    for(i=l; i<=r; i++)
        if(data[d][i]<sorted[m])
            ls -- ;         //踢掉比中间值小的
        int lp = l ;
        int rp = m + 1 ;
        for(i=l; i<=r; i++){
            if(i==l)
                toleft[d][i] = 0 ; //// 初始一个子树。
            else
                toleft[d][i] = toleft[d][i-1] ; //// 初始区间下一个节点。

            /* 如果大于，肯定进入右孩子，否则，判断是否还有相等的应该进入左孩子的，
               没有，就直接进入右孩子，否则进入左孩子*/
            if(data[d][i]<sorted[m]){
                toleft[d][i]++;
                data[d+1][lp++] = data[d][i] ;
            }else if(data[d][i]>sorted[m])
                data[d+1][rp++] = data[d][i] ;
            else{                      //考虑相等
                if(ls){               // 相等分到做孩子的数目>0
                    ls -- ;
                    toleft[d][i]++ ;
                    data[d+1][lp++] = data[d][i] ;
                }else data[d+1][rp++] = data[d][i] ;
            }
        }
        build(l, m, d+1) ;
        build(m+1, r, d+1) ;
}
int query(int L, int R, int k, int l, int r, int d){ //在[L,R]区间寻找小于第k 的元素，总区间[l,r]
    if(L==R)    return data[d][L] ;
    int m = (l + r) >> 1 ;
    int lLR, llL, rLR, rlL ;
    if(L==l){
        lLR = toleft[d][R] ;   //lLR 左边小于第k个元素的数量
        llL = 0 ;             //llL 记录区间[lft, a-1)中计入左孩子的元素的个数。
    }else{
        lLR = toleft[d][R] - toleft[d][L-1] ; //
        llL = toleft[d][L-1] ;
    }
    int nl, nr ;
    if(lLR>=k){
        nl = l + llL ;       //记录区间[L, R]中进入左孩子的元素的个数。
        nr = l + lLR + llL - 1 ; //
        return query(nl, nr, k, l, m, d+1) ;
    }else{
        rlL = L - l - llL ;       //表示[L, R] 中分到右孩子的个数
        rLR = R - L + 1 - lLR ; //表示[lft, a-1]中分到右孩子的个数
        nl = m + 1 + rlL ;
        nr = m + rlL + rLR ;
        return query(nl, nr, k-lLR, m+1, r, d+1) ;
    }
}

int main(){
    int n, m, i, j, l, r, k ;
    while(~scanf("%d%d",&n,&m)){
        for(i=1; i<=n; i++){
            scanf("%d",&data[0][i] );
            sorted[i] = data[0][i] ;
        }
        qsort(sorted+1, n, sizeof(int), cmp) ;
        build(1, n, 0);
        while(m--){
            scanf("%d%d%d", &l, &r, &k) ;
            printf("%d\n",query(l, r, k, 1, n, 0)) ;
        }
    }
    return 0 ;
}

补充：软件开发 , C++ ,