记录编号	407974	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	3.157 s
提交时间	2017-05-23 16:17:49	内存使用	77.75 MiB

#include <iostream>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <time.h>
#include <map>
#include <deque>
#include <string>
using namespace std;
int n,t;
int ppp[100010];
int data[100010];
int hash[100100];
int tot;
int ls[5000010];
int rs[5000010];
int sum[5000010];
int gen[5000010];
int dian;
inline bool cmp(int a,int b)
{
	return a>b;
}
inline int erfen(int x)
{
	int l=1;int r=tot;
	while(l+1<r)
	{
		int m=(l+r)/2;
		if(x<hash[m])l=m+1;
		else r=m;
	}
	if(hash[l]==x)return l;
	return r;
}
inline void gai(int shang,int &xin,int l,int r,int nl,int nr)
{
	xin=++dian;
	if(l>=nl&&r<=nr)
	{
		sum[xin]=sum[shang]+1;
		return ;
	}
	ls[xin]=ls[shang];
	rs[xin]=rs[shang];
	int m=(l+r)>>1;
	if(m>=nl)
	{
		gai(ls[shang],ls[xin],l,m,nl,nr);
	}
	if(m<nr)
	{
		gai(rs[shang],rs[xin],m+1,r,nl,nr);
	}
	sum[xin]=sum[ls[xin]]+sum[rs[xin]];
}
inline int find(int shang,int xin,int l,int r,int k)
{
	if(l==r)
	{
		return l;
	}
	//int zuo=sum[ls[shang]]-sum[ls[xin]];
	int you=sum[rs[xin]]-sum[rs[shang]];
	int m=(l+r)>>1;
	if(you>=k)
	{
		return find(rs[shang],rs[xin],m+1,r,k);
	}
	else
	{
		return find(ls[shang],ls[xin],l,m,k-you);
	}
}
int main()
{
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
	ios::sync_with_stdio(false);
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&ppp[i]);
		data[i]=ppp[i];
	}
	sort(ppp+1,ppp+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		if(ppp[i]!=ppp[i-1])
		{
			hash[++tot]=ppp[i];
		}
	}
	for(int i=1;i<=n;i++)
	{
		int u=erfen(data[i]);
		gai(gen[i-1],gen[i],1,tot,u,u);
	}
	while(t--)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		printf("%d\n",hash[find(gen[x-1],gen[y],1,tot,z)]);
		//cout<<x<<y<<z<<" "<<find(gen[x-1],gen[y],1,tot,z)<<endl;
	}
	return 0;
}