题意：
给出一数组a，然后要求查询a[i..j]的第k大的数。
算法：
继续我的学习数据结构的步伐，之前学习了后缀数组，今天继而学习另一个有用的统计工具，归并树。
实际上归并树，就是把归并排序的过程记录下来。也算是一个线段树吧，但是节点的记录了该区间[i,j]的排序后的结果。先不要考虑空间复杂度，如果可以在每个节点放有该区间排序后的结果，那么我们把查询的区间去查找，就是像线段树的查找一样，要查询的数k在各个区间中有多少个数小于k，然后相加起来，这样，便可以得到该区间中，k这个数有多少个数小于k。因此我们把数组排序后二分，便可以找到结果。
归并树：
刚才考虑到线段树不可能每个节点都存放排序后的结果，因为在每个节点中，我们都需要O(n)的空间，但是有些点的数组小，开O(n)的数组剩余太大，考虑到这里我们就放弃在线段树的节点里存放。我们只需要在线段树的每个深度开一个o(n)的数组就可以了。
至于怎么写归并树：
参看网上的代码（写得很好）：http://www.cnblogs.com/zgmf_x20a/archive/2008/11/15/1333968.html
代码：
#include<cstdio>
using namespace std;
#define MAX 100005
int key[MAX];
int n,m;
struct node{
int l,r;
};
node a[MAX*5];
int mergetree[25][MAX];
void build(int l,int r,int id,int depth){
if(l>r)return;
if(l==r){
a[id].l=a[id].r=l;
mergetree[depth][l]=key[l];
return;
}
int mid=(l+r)>>1;
a[id].l=l;
a[id].r=r;
build(l,mid,id*2,depth+1);
build(mid+1,r,id*2+1,depth+1);
int i=l,j=mid+1;
int k=l;
while(i<=mid&&j<=r){
if(mergetree[depth+1][i]<=mergetree[depth+1][j])mergetree[depth][k++]=mergetree[depth+1][i++];
else mergetree[depth][k++]=mergetree[depth+1][j++];
}
if(i>mid){
while(j<=r)mergetree[depth][k++]=mergetree[depth+1][j++];
}
if(j>r){
while(i<=mid)mergetree[depth][k++]=mergetree[depth+1][i++];
}
}
int query(int id,int l,int r,int k,int depth){
if(a[id].l==l&&a[id].r==r){
int bottom=l,top=r;
if(mergetree[depth][bottom]>=k)return 0;
if(mergetree[depth][top]<k)return r-l+1;
while(bottom<top){
if(bottom==top-1){
if(mergetree[depth][top]>=k)top=bottom;
break;
}
int mid=(bottom+top)>>1;
if(mergetree[depth][mid]>=k)top=mid-1;
else bottom=mid;
}
return top-l+1;
}
int mid=(a[id].l+a[id].r)>>1;
if(l<=mid){
if(r>mid)return query(id*2,l,mid,k,depth+1)+query(id*2+1,mid+1,r,k,depth+1);
else return query(id*2,l,r,k,depth+1);
}
else return query(id*2+1,l,r,k,depth+1);
}
int solve(int l,int r,int rank){
int bottom=1,top=n;
rank--;
if(query(1,l,r,mergetree[0][n],0)==rank)return mergetree[0][n];
while(bottom<top){
int mid=(bottom+top)>>1;
int k=query(1,l,r,mergetree[0][mid],0);
if(k<=rank)bottom=mid+1;
else top=mid;
}
return mergetree[0][top-1];
}
int main(){
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;i++)scanf("%d",&key[i]);
build(1,n,1,0);
for(i=0;i<m;i++){
int x,y,rank;
scanf("%d%d%d",&x,&y,&rank);
printf("%d\n",solve(x,y,rank));
}
return 0;
}