记录编号	454919	评测结果	AAAAAATTTTAAAAAAAAAAATTATAAAAA
题目名称	[NEERC 2004] K小数	最终得分	76
用户昵称	~玖湫~	是否通过	未通过
代码语言	C++	运行时间	18.450 s
提交时间	2017-09-30 11:29:46	内存使用	2.89 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int M=100000+10;
const int qrt=330;
#define size(x) (((x)!=NULL)?(x->siz):(0))
int n,m;
int val[M],ans[M],block[M];
struct DATE{int l,r,id,k;}date[M];
inline bool cmp(DATE a,DATE b) {return block[a.l]==block[b.l]?a.r<b.r:block[a.l]<block[b.l];}
struct treap{
	treap* ch[2];
	int val,key,siz;
	inline treap(int v) {siz=1;key=rand();val=v;ch[0]=ch[1]=NULL;}
	inline void update() {siz=1+size(ch[0])+size(ch[1]);}
}*rt;
typedef pair<treap*,treap*> dou;
inline treap* merge(treap* a,treap* b){
	if(!a) return b; if(!b) return a;
	if(a->key<b->key){
		a->ch[1]=merge(a->ch[1],b);
		a->update();return a;
	}else{
		b->ch[0]=merge(a,b->ch[0]);
		b->update();return b;
	}
}
inline dou split(treap* o,int k){
	if(!o) return dou(NULL,NULL);
	dou x;
	if(size(o->ch[0])>=k){
		x=split(o->ch[0],k);
		o->ch[0]=x.second;o->update();x.second=o;
	}else{
		x=split(o->ch[1],k-1-size(o->ch[0]));
		o->ch[1]=x.first;o->update();x.first=o;
	}return x;
}
inline int getrank(treap* o,int v){
	if(!o) return 0;
	if(o->val>=v) return getrank(o->ch[0],v);
	return getrank(o->ch[1],v)+1+size(o->ch[0]);
}
inline int findrank(int k){
	dou x=split(rt,k-1);
	dou y=split(x.second,1);
	treap* ans=y.first;
	rt=merge(x.first,merge(y.first,y.second));
	return ans?ans->val:0;
}
inline void _insert(int v){
	int k=getrank(rt,v);
	dou x=split(rt,k);
	treap* ans=new treap(v);
	rt=merge(x.first,merge(ans,x.second));
}
inline void _delete(int v){
	int k=getrank(rt,v);
	dou x=split(rt,k);
	dou y=split(x.second,1);
	rt=merge(x.first,y.second);
}
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int DK(){
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
	n=read();m=read();int xx,yy,k;
	for(int i=1;i<=n;++i) val[i]=read(),block[i]=(i-1)/qrt+1;
	for(int i=1;i<=m;++i){
		date[i].l=read();date[i].r=read();
		date[i].id=i;date[i].k=read();
	}sort(date+1,date+m+1,cmp);
	int l=1,r=0;
	for(int i=1;i<=m;++i){
		int L=date[i].l,R=date[i].r;
		for(;r<R;++r) _insert(val[r+1]);
		for(;r>R;--r) _delete(val[r]);
		for(;l<L;++l) _delete(val[l]);
		for(;l>L;--l) _insert(val[l-1]);
		ans[date[i].id]=findrank(date[i].k);
	}
	for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
	return 0; 
}
int dk=DK();
int main(){;}