学习了网上最常用的解法——归并树。
所谓的归并树并不是什么新奇的东西，顾名思义，其实就是归并排序+线段树。把归并排序过程中的各区间排序后的结果，用线段树储存起来！
对题目给定的区间，只要在线段树中查找组成该区间的各个子区间即可！——logN
关键在于求出某个值在线段树各个子区间中，小于该值的元素个数，还是用到了二分，继续是logN。
由于要求的是该区间的第k小元素，可以对整个排序完的数组进行二分查找，当某元素在该区间中排第k小，并且该元素属于该区间，即为答案。对排序数组进行二分查找，也是logN。
耗时：2500ms+
#include<stdio.h>
#define N 100010
struct T
{
int l,r,mid;
}t[N*4];
int sort[20][N];
int id[20][N];
int key[N],s,e;
int build(int p,int l,int r,int dep)
{
t[p].l=l;
t[p].r=r;
t[p].mid=(l+r)>>1;
if(l==r)
{
sort[dep][l]=key[l];
id[dep][l]=l;
return 0;
}
build(p<<1,l,t[p].mid,dep+1);
build((p<<1)+1,t[p].mid+1,r,dep+1);
int i,j,mid,now;
mid=t[p].mid;
i=l; j=mid+1; now=l;
while(i<=mid && j<=r)
{
if(sort[dep+1][i]<sort[dep+1][j])
{
id[dep][now]=id[dep+1][i];
sort[dep][now++]=sort[dep+1][i++];
}
else
{
id[dep][now]=id[dep+1][j];
sort[dep][now++]=sort[dep+1][j++];
}
}
if(i==mid+1)
while(j<=r)
{
id[dep][now]=id[dep+1][j];
sort[dep][now++]=sort[dep+1][j++];
}
else
while(i<=mid)
{
id[dep][now]=id[dep+1][i];
sort[dep][now++]=sort[dep+1][i++];
}
return 0;
}
int b_search(int left,int right,int v,int dep)
{
int l,r,m;
l=left;r=right;
if(v<=sort[dep][l])
return 0;
else if(v>sort[dep][r])
return (r-l+1);
while(l<r)
{
m=(l+r)>>1;
if(sort[dep][m]>=v && sort[dep][m-1]<v)
return m-left;
if(sort[dep][m]<v)
l=m+1;
else
r=m;
}
return l-left;
}
int query(int p,int v,int dep)
{
if(s<=t[p].l && t[p].r<=e)
{
return b_search(t[p].l,t[p].r,v,dep);
}
else
{
if(s>t[p].r || e<t[p].l)
return 0;
return query(p<<1,v,dep+1)+query((p<<1)+1,v,dep+1);
}
}
int main()
{
// freopen("1.txt","r",stdin);
int n,q,i,j,k,left,right,mid,result,p;
while(scanf("%d %d",&n,&q)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&key[i]);
build(1,1,n,1);
while(q--)
{
scanf("%d %d %d",&s,&e,&k);
left=1; right=n;
k--;
p=0;
while(left<right)
{
mid=(left+right+1)>>1;
result=query(1,sort[1][mid],1);
if(result==k && id[1][mid]>=s && id[1][mid]<=e)
{
p=1;
printf("%d\n",sort[1][mid]);
break;
}
if(result<=k)
left=mid;
else
right=mid-1;
}
if(!p)
printf("%d\n",sort[1][left]);
}
}
return 0;
}