poj2104 K-th Number

划分树。

实际上相当于把数列归并排序的过程用树形结构储存起来，并通过一个辅助二位数组记录数的每一层上的每一个元素被划分到子树的情况（划分到左子树

或右子树）。

归并排序具有稳定性，这也是能够准确查询k-th元素的关键。

通过辅助数组在树形结构中不断判断第k个元素属于哪个子树哪个区间，最终找到此元素。

http://poj.org/problem?id=2104

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 10;
const int maxd = 22;

int tree[maxd][maxn], left[maxd][maxn];
int s[maxn];
int n, m, l, r, k;

void build(int d, int l, int r){
    if(r - l < 2) return;
    int mid = (l + r) >> 1;
    int left_mid = mid - l;
    for(int i = l; i < r; i++) if(tree[d][i] < s[mid]) left_mid--;
    int ls = l, rs = mid;
    for(int i = l; i < r; i++){
        int flag = 1;
        if(tree[d][i] < s[mid])    tree[d + 1][ls++] = tree[d][i];
        else if(tree[d][i] == s[mid] && left_mid) tree[d + 1][ls++] = tree[d][i], --left_mid;
        else tree[d + 1][rs++] = tree[d][i], flag = 0;
        left[d][i + 1] = left[d][i] + flag;
    }
    build(d + 1, l, mid);
    build(d + 1, mid, r);
}

int query(int k, int l, int r, int d, int L, int R){
    //find the k-th number in range[l, r) within tree of depth d
    if(r - l < 2) return tree[d][l];
    int Ll1 = left[d][l] - left[d][L];
    //num of elements in range [L, l) divided into left-subtree
    int Lr1 = left[d][r] - left[d][L];
    int Ll2 = l - L - (left[d][l] - left[d][L]);
    int Lr2 = r - L - (left[d][r] - left[d][L]);
    int mid = (L + R) >> 1;
    int cnt_left = Lr1 - Ll1;
    if(cnt_left >= k) return query(k, L + Ll1, L + Lr1, d + 1, L, mid);
    else return query(k - cnt_left, mid + Ll2, mid + Lr2, d + 1, mid, R);
}

int main(){
    while(~scanf("%d%d", &n, &m)){
        for(int i = 0; i < n; i++){
            scanf("%d", &s[i]);
            tree[0][i] = s[i];
        }
        sort(s, s + n);
        for(int i = 0; i < maxd; i++) left[i][0] = 0;
        build(0, 0, n);
        for(int i = 0; i < m; i++){
            scanf("%d%d%d", &l, &r, &k);
            int ans = query(k, l - 1, r, 0, 0, n);
            printf("%d
", ans);
        }
    }
    return 0;
}