记录编号	283413	评测结果	AAAAAAAAAA
题目名称	930.[河南省队2012] 找第k小的数	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.980 s
提交时间	2016-07-14 17:29:31	内存使用	1.83 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
	int l,r,sum;
	node *lch,*rch;
	node(){
	}
	node(int L,int R){
		lch=rch=NULL;
		sum=0;l=L;r=R;
	}
};
node* root[100005];
int a[100005],seq[100005],rank[100005];
bool cmp(const int &x,const int &y){
	return a[x]<a[y];
}
void build0(node* rt){
	if(rt->l==rt->r)return;
	int mid=(rt->l+rt->r)>>1;
	rt->lch=new node(rt->l,mid);
	rt->rch=new node(mid+1,rt->r);
	build0(rt->lch);build0(rt->rch);
}
void Add(node *rt1,node *rt2,int k){
	if(rt2->l==rt2->r){
		rt2->sum=1;
		return;
	}
	int mid=(rt1->l+rt1->r)>>1;
	if(k<=mid){
		rt2->rch=rt1->rch;
		rt2->lch=new node(rt2->l,mid);
		Add(rt1->lch,rt2->lch,k);
	}
	else{
		rt2->lch=rt1->lch;
		rt2->rch=new node(mid+1,rt2->r);
		Add(rt1->rch,rt2->rch,k);
	}
	rt2->sum=rt2->lch->sum+rt2->rch->sum;
}
int query(node *rt1,node *rt2,int kth){
	if(rt1->l==rt1->r)return rt1->l;
	int tmp=rt2->lch->sum-rt1->lch->sum;
	if(tmp>=kth)return query(rt1->lch,rt2->lch,kth);
	else return query(rt1->rch,rt2->rch,kth-tmp);
}
int main(){
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);seq[i]=i;
	}
	sort(seq+1,seq+n+1,cmp);
	for(int i=1;i<=n;++i){
		rank[seq[i]]=i;
	}
	root[0]=new node(1,n);
	build0(root[0]);
	for(int i=1;i<=n;++i){
		root[i]=new node(1,n);
		Add(root[i-1],root[i],rank[i]);//注意：从i-1的基础上添加，不是从0 
	}
	int left,right,k;
	while(m--){
		scanf("%d %d %d",&left,&right,&k);
		printf("%d\n",a[seq[query(root[left-1],root[right],k)]]);
	}
	fclose(stdin);fclose(stdout);
	return 0;
}