记录编号	234714	评测结果	EEEEEETTTTEEEEEAEEEEEATTTTTTTT
题目名称	[NEERC 2004] K小数	最终得分	6
用户昵称	liu_runda	是否通过	未通过
代码语言	C++	运行时间	26.197 s
提交时间	2016-03-09 09:24:48	内存使用	2.72 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int data[100005];
int buf[100005];
int read(){
	int x;char ch;bool minus=false;
	while(ch=getchar(),(ch>'9'||ch<'0')&&ch!='-');
	if(ch=='-'){
		minus=true;
		ch=getchar();
	}
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return minus?-x:x;
}
int query(int l,int r,int k){
//	printf("q(%d %d %d)\n",l,r,k);
//	for(int i=1;i<r;++i)printf("%d ",buf[i]);
//	printf("\n");
	if(r-l<=1)return buf[l];
	int mid=(l+r)>>1;
	int part=buf[mid];
//	printf("%d %d\n",mid,part);
	int left=l,right=r-1;
	while(left<right){
		while(left<mid&&buf[left]<=part)left++;
	//	printf("move %d to %d\n",left,mid);
		buf[mid]=buf[left];mid=left;
		while(mid<right&&buf[right]>=part)right--;
	//	printf("move %d to %d\n",right,mid);
		buf[mid]=buf[right];mid=right;
		
	}
	buf[mid]=part;
	if(k==mid-l+1)return part;
	else if(k<mid-l+1)return query(l,mid,k);
	else return query(mid+1,r,k-(mid-l+1));
}
int main(){
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
	int n=read(),m=read();
	for(int i=1;i<=n;++i){
		data[i]=read();
	}
	int x,y,k;
	for(int i=1;i<=m;++i){
		x=read();y=read();k=read();
		memcpy(buf+1,data+x,sizeof(int)*(y-x+1));
		printf("%d\n",query(1,y-x+2,k));
	}
	fclose(stdin);fclose(stdout);
	return 0;
}
/*
5 35
-129439731 -871827100 -64049111 -972971727 511418813
*/