记录编号	419841	评测结果	AAAAAAAAAA
题目名称	[河南省队2012] 找第k小的数	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	2.311 s
提交时间	2017-07-03 15:50:47	内存使用	1.07 MiB

#include<cstdio>
#include<cctype>
#define mid_a ((l+r)>>1)
#define mid_b ((now->ls->r))
const int maxn=100023;
using namespace std;
struct pstree
{
	int l,r;
	int num;
	pstree *ls,*rs;
	pstree(){ls=rs=NULL;num=l=r=0;}
}*root[maxn];
int n,m;
int N[maxn],Mx;
int a,b,k;
inline int get();
pstree* build(int l,int r);
pstree* add(int nu,pstree *now);
int search(pstree *now_a,pstree *now_b,int k);
int main()
{
	freopen("kth.in","r",stdin);
	freopen("kth.out","w",stdout);
	n=get();m=get();
	for(int i=1;i<=n;i++)
	{
		N[i]=get();
		if(N[i]>Mx)Mx=N[i];
	}
	root[0]=build(1,Mx);
	for(int i=1;i<=n;i++)root[i]=add(N[i],root[i-1]);
	for(int i=1;i<=m;i++)
	{
		a=get();b=get();k=get();
		printf("%d\n",search(root[b],root[a-1],k));
	}
	return 0;
}
int search(pstree *now_a,pstree *now_b,int k)
{
	if(now_a->ls==NULL)return now_a->l;
	int va_ls=now_a->ls->num-now_b->ls->num;
	if(k<=va_ls)return search(now_a->ls,now_b->ls,k);
	else return search(now_a->rs,now_b->rs,k-va_ls);
}
pstree* add(int nu,pstree *now)
{
	pstree *p=new pstree();
	p->l=now->l;p->r=now->r;p->num=now->num;
	if(now->l==nu&&now->ls==NULL)
	{
		p->num++;
		return p;
	}
	if(nu<=mid_b)
	{
		p->ls=add(nu,now->ls);
		p->rs=now->rs;
	}
	else
	{
		p->ls=now->ls;
		p->rs=add(nu,now->rs);
	}
	p->num=p->ls->num+p->rs->num;
	return p;
}
pstree* build(int l,int r)
{
	pstree *p=new pstree();
	p->l=l;p->r=r;
	if(l==r)return p;
	p->ls=build(l,mid_a);
	p->rs=build(mid_a+1,r);
	return p;
}
inline int get()
{
	int t=0,jud=1;char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')jud=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		t=(t<<3)+(t<<1)+c-'0';
		c=getchar();
	}
	return t*jud;
}