记录编号	457296	评测结果	AAAAAAAAAA
题目名称	930.[河南省队2012] 找第k小的数	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.897 s
提交时间	2017-10-07 15:59:31	内存使用	25.11 MiB

#include<bits/stdc++.h>//第一次码qwq按自己理解来了 
#define mid ((l+r)>>1)//其实我觉得更多的是平衡树(儿茶搜索树)而不是线段树 
using namespace std;
int n,m,a[100005],root[100005],f_cnt,hs[100005];
struct node{
	int ls,rs,sum;
}f[2000005];
struct hh{
	int val,id;//非严格第k小 
	bool operator < (const hh &o)const{
		return val<o.val;
	}
}b[100005];
void insert(int l,int r,int now,int x){
	f[now].sum++;if(l==r)return ;
	if(x>mid){
		f[++f_cnt]=f[f[now].rs];f[now].rs=f_cnt;
		insert(mid+1,r,f_cnt,x);
	}
	else {
		f[++f_cnt]=f[f[now].ls];f[now].ls=f_cnt;
		insert(l,mid,f_cnt,x);
	}
}
int query(int l,int r,int x,int y,int k){
	if(l==r)return l;
	int tem=f[f[y].ls].sum-f[f[x].ls].sum;
	if(tem<k)return query(mid+1,r,f[x].rs,f[y].rs,k-tem);
	else return query(l,mid,f[x].ls,f[y].ls,k);
}
int main()
{
	freopen("kth.in","r",stdin);freopen("kth.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&b[i].val),b[i].id=i;
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)a[b[i].id]=i;
	root[0]=0;
	for(int i=1;i<=n;i++){
		root[i]=++f_cnt;
		f[root[i]]=f[root[i-1]];
		insert(1,n,root[i],a[i]);
	}
	for(int i=1;i<=m;i++){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",b[query(1,n,root[l-1],root[r],k)].val);
	}
	return 0;
}