记录编号	308751	评测结果	AAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2016-09-18 17:09:58	内存使用	21.28 MiB

#include<cstdio>
#include<algorithm>

//#include <windows.h>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Betin freopen("kthnumber.in","r",stdin);freopen("kthnumber.out","w",stdout);
#define Begin Betin;chul();Cu;
using namespace std;
typedef long long ll;
const int maxn=1010;
const ll INF=~0ULL>>2;
ll a[maxn*maxn],tub[maxn*maxn],tsd[maxn*maxn];
ll n,s,t,k;
ll ntub,b;
ll getsqrt(ll x){
	ll l=1,r=x;
	ll mid,ans=l;
	while(l<r){
		mid=(l+r)>>1;
		if(mid*mid<x){
			ans=mid;
			l=mid+1;
		}
		else r=mid;
	}
	return ans;
} 
int JUDGE(ll x){
	ll l=s,r=t,cnt=0;
	while(((l)%b)&&l<=r){
		if(a[l]<x){
			cnt++;
		}
		//printf("l:::%d\n",l+1);
		l++;
	}
	while(((r+1)%b)&&l<=r){
		if(a[r]<x){
			cnt++;
		}
		//printf("r:::%lld\n",r+1);
		r--;
	}//printf("-->%d ",cnt);
	
	if(l<r)
		for(ll i=l/b;i<=r/b;i++){
			ll poi=lower_bound(tub+i*b,tub+i*b+b,x)-tub;
		//	printf("poi:::%lld\n",poi);
			cnt+=(poi-i*b);
		}
	return cnt;
}
void chul(){
	ll m;scanf("%lld%lld",&n,&m);
	ntub=getsqrt(n);
	b=n/ntub;
	for(ll i=0;i<n;i++){
		scanf("%lld",&a[i]);
		tub[i]=a[i];
		tsd[i+1]=a[i];
	}
	for(ll i=0;i<ntub;i++){
		sort(tub+i*b,tub+i*b+b);
	}
	sort(tsd+1,tsd+1+n);
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld%lld",&s,&t,&k);
		ll ans=1,mid;
		s--;t--;
		if(s==t){
			printf("%lld\n",a[s]);
			continue;
		}
		ll l=-INF,r=INF;
		while(l<=r){
			mid=(l+r)>>1LL;
			int cnt=JUDGE(mid);
			//printf("HERE");
			//if(s==0&&t==1&&k==2)printf("l:%lld  mid:%lld(%d) r:%lld \n",l,mid,cnt,r),	Sleep(50);
			if(cnt<k)ans=mid,l=mid+1;
			else r=mid-1;
			
		}
	//	if(JUDGE(tsd[ans-1]))ans=ans-1;
		printf("%lld\n",ans);
		
	
	}
	//while(getchar()!='e');
}
int main(){
	Begin;
}