记录编号	88988	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	noip	是否通过	通过
代码语言	C++	运行时间	1.453 s
提交时间	2014-02-27 07:15:52	内存使用	71.27 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
int tree[30][300010];
int s[30][300010];
int a[300010],sa[300010];
int bt(int x,int y,int z)
{
	int m=(y+z)/2;
	int p=0,t,nl=y,nr=m+1;
	for(t=y;t<=m;t++)
		if(sa[t]==sa[m])
			p++;
	
	for(t=y;t<=z;t++)
	{
		if(t==y)
			s[x][t]=0;
		else
			s[x][t]=s[x][t-1];
		if(tree[x][t]<sa[m])
		{
			tree[x+1][nl]=tree[x][t];
			s[x][t]++;
			nl++;
		}
		else
			if(tree[x][t]>sa[m])
			{
				tree[x+1][nr]=tree[x][t];
				nr++;
			}
			else
				if(p)
				{
					tree[x+1][nl]=tree[x][t];
					s[x][t]++;
					nl++;
					p--;
				}
				else
				{
					tree[x+1][nr]=tree[x][t];
					nr++;
				}
	}
	if(y!=z)
	{
		bt(x+1,y,m);
		bt(x+1,m+1,z);
	}
}
int get(int x,int l,int r,int ql,int qr,int k)
{
	int sl,sr;
	if(l==r)
		return tree[x][l];
	if(ql==l)
	{
		sl=0;
		sr=s[x][qr];
	}
	else
	{
		sl=s[x][ql-1];
		sr=s[x][qr];
	}
	if(sr-sl>=k)
		return get(x+1,l,(l+r)/2,l+sl,l+sr-1,k);
	else
		return get(x+1,(l+r)/2+1,r,(l+r)/2+1+ql-l-sl,(l+r)/2+1+qr-l-sr,k-sr+sl);
}
int main()
{
    freopen("kthnumber.in","r",stdin);
    freopen("kthnumber.out","w",stdout);
	int n,m,n1,m1,t1,t2,t3;
	cin>>n>>m;
	for(n1=1;n1<=n;n1++)
	{
		scanf("%d",&a[n1]);
		tree[0][n1]=sa[n1]=a[n1];
	}
	sort(sa+1,sa+n+1);
	bt(0,1,n);
	for(m1=1;m1<=m;m1++)
	{
		scanf("%d%d%d",&t1,&t2,&t3);
		printf("%d\n",get(0,1,n,t1,t2,t3));
	}
}