记录编号	366345	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	1534.[NEERC 2004] K小数	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.062 s
提交时间	2017-01-23 17:46:22	内存使用	17.61 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,q,a[N],s[20][N],T[20][N];
void build(int h,int l,int r){
	int *x=T[h],*y=T[h+1];
	if (l==r){y[l]=x[l];return;}
	int mid=(l+r)>>1,flag=a[mid],cnt=l,p=l,q=mid+1;
	for (int i=l;i<=r;i++)
		if (x[i]<flag) cnt++;
	for (int i=l;i<=r;i++){
		s[h][i]=(i==l?0:s[h][i-1]);
		if (x[i]<flag) y[p++]=x[i],s[h][i]++;else
		if (x[i]==flag&&cnt<=mid) y[p++]=x[i],s[h][i]++,cnt++;
			else y[q++]=x[i];
	}
	build(h+1,l,mid);
	build(h+1,mid+1,r);
}
int ask(int h,int l,int r,int L,int R,int k){
	if (L==R) return T[h][L];
	int mid=(l+r)>>1,cl=(l==L?0:s[h][L-1]),cr=s[h][R];
	if (k<=cr-cl) return ask(h+1,l,mid,l+cl,l+cr-1,k);
	return ask(h+1,mid+1,r,mid+1+L-l-cl,mid+1+R-l-cr,k-cr+cl);
}
int main()
{
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]),T[0][i]=a[i];
	sort(a+1,a+n+1);
	build(0,1,n);
	while (q--){
		int l,r,k;
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",ask(0,1,n,l,r,k));
	}
	return 0;
}