POJ 2104 归并树 or 划分树
首先写一下归并树的版本吧
归并树实际上是一种类似于归并排序外加线段树的东西
用到线段树的地方就是划分区间。
我们都知道，线段树是一层一层这样下来的，每层上有若干个区间。
归并树的作用就是，对每一层上的所有区间，其内部都是排好序的。
也就是说，第一层是所有数排好序，第二层划分了两个子区间，两个子区间内部都是排好序的。依次直到叶子结点
当然，建树的过程跟线段树是一样的，只不过在递归的过程中要将子区间的信息归并到父区间时要是用归并排序的归并操作。


建好树之后就是查询操作了
这就要说到这道题的另一个做法，快排的做法
快排做法就是把序列进行排序，然后每次询问，都把序列扫一遍，用一个变量表示扫到了查询区间的第几小的数，如果一个位置属于查询区间的，就自增，这样直到变量为K时结束
因为我们已经排好序了，所以这种做法必然是可行的。只不过实在是速度太慢。
归并树的做法也是基于这种思想来搞的。
只不过建树后就可以进行二分操作。
我们还是先排好了序，然后二分，看二分的这个值在查询区间中能排到第几小，当查询到某个值使得在查询区间中恰好为第K小时，即为所求。
那么怎么计算他在查询区间中排第几呢，用到了归并树。
在归并树中，你查询的区间必然能被树上某些区间的并来表示，在这些区间当中，由于我们已经排好了序，所以又可以进行二分查找，来找出比我们第一层二分的值小的元素有多少个。
注意，第一层二分的值很有可能不在查询区间中，而也为查询区间的第K小，这就要我们取那个从k-1刚变为k时的那个值


总的复杂度是m*logn*logn*logn的 二分边界也非常蛋疼 不好写

#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <set>#define eps 1e-5#define MAXN 111111#define MAXM 1111111#define INF 1000000008using namespace std;int a[MAXN], p[MAXN], rank[MAXN], lnum[20][MAXN], t[MAXN];int n, q;bool cmp(int x, int y){    if(a[x] != a[y]) return a[x] < a[y];    else return x < y;}void build(int l, int r, int deep){    if(l == r) return;    int m = (l + r) >> 1;    int cnt = 0, j = l, k = m + 1;    for(int i = l; i <= r; i++)    {        if(rank[i] <= m) t[j++] = rank[i], lnum[deep][i] = ++cnt;        else t[k++] = rank[i], lnum[deep][i] = cnt;    }    for(int i = l; i <= r; i++) rank[i] = t[i];    build(l, m, deep + 1);    build(m + 1, r, deep + 1);}int query(int L, int R, int l, int r, int k, int deep){    if(l == r) return a[p[l]];    int m = (l + r) >> 1;    int tl = 0;    if(l < L) tl = lnum[deep][L - 1];    int tn = lnum[deep][R] - tl;    if(tn >= k) return query(l + tl, l + tl + tn - 1, l, m, k, deep + 1);    else    {        int pos = m + L - l - tl + 1;// L-l-tl表示从l到L-1有多少个分到了右孩子        return query(pos, pos + R - L - tn, m + 1 ,r , k - tn, deep + 1);     }}int main(){    while(scanf("%d%d", &n, &q) != EOF)    {        for(int i = 1; i <= n; i++) scanf("%d", &a[i]), p[i] = i;        sort(p + 1, p + n + 1, cmp);        for(int i = 1; i <= n; i++) rank[p[i]] = i;        build(1, n, 1);        int x, y, z;        while(q--)        {            scanf("%d%d%d", &x, &y, &z);            printf("%d\n", query(x, y, 1, n, z, 1));        }    }    return 0;}