记录编号	454969	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	1.525 s
提交时间	2017-09-30 17:51:31	内存使用	1.07 MiB

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100005
#define inf 1000000
using namespace std;
int n,m,a[N];
namespace chairtree
{
	struct tree
	{
		tree* lc;tree* rc;
		int sum;
		tree(){lc=rc=NULL;sum=0;}
	}*null=new tree(),*root[N];
	tree* newtree()
	{
		tree* o=new tree();
		o->lc=o->rc=null;
		o->sum=0;
		return o;
	}
	void build(int l,int r,tree* &x)
	{
		x=newtree();
		if(l==r){return;}
		int mid=l+r>>1;
		build(l,mid,x->lc);
		build(mid+1,r,x->rc);
	}
	void insert(int l,int r,tree* &x,tree* pre,int k)
	{
		x->sum=pre->sum+1;
		if(l==r){return;}
		int mid=l+r>>1;
		if(k<=mid)x->lc=newtree(),x->rc=pre->rc,insert(l,mid,x->lc,pre->lc,k);
		else x->rc=newtree(),x->lc=pre->lc,insert(mid+1,r,x->rc,pre->rc,k);
	}
	int q(int l,int r,tree* x1,tree* x2,int k)
	{
		int mid,cmp;
		while(l<r)
		{
			mid=l+r>>1;
			cmp=x2->lc->sum-x1->lc->sum;
			if(cmp>=k)
			{
				r=mid;x1=x1->lc;x2=x2->lc;
			}
			else
			{
				l=mid+1;k-=cmp;x1=x1->rc;x2=x2->rc;
			}
		}
		return r;
	}
}
using namespace chairtree;
int main()
{
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
	scanf("%d%d",&n,&m);null->lc=null->rc=null;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),root[i]=newtree();
	root[0]=newtree();
	for(int i=1;i<=n;i++)insert(-inf,inf,root[i],root[i-1],a[i]);//cout<<root[1]->rc->sum<<endl;
	int l,r,k;
	while(m--)
	{
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",q(-inf,inf,root[l-1],root[r],k));
	}
}