记录编号	308785	评测结果	AAAAAATTTTAAAAAAAAAAAAAAAAAAAA
题目名称	[NEERC 2004] K小数	最终得分	86
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	20.078 s
提交时间	2016-09-18 17:37:33	内存使用	1.83 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int maxn=100010;
struct node{
	int data,size;
	node *lc,*rc,*prt;
	node(int d=0):data(d),size(1),lc(NULL),rc(NULL),prt(NULL){}
	void refresh(){
		size=1;
		if(lc)size+=lc->size;
		if(rc)size+=rc->size;
	}
}*root[maxn<<2]={NULL};
void build(int,int,int);
void query(int,int,int);
void insert(node*,int);
void copy(int,node*);
int rank(int,int);
void splay(node*,node*,int);
void lrot(node*,int);
void rrot(node*,int);
int n,m,x,l,r,k,s,t,tmp,ans;
int main(){
#define MINE
#ifdef MINE
	freopen("kthnumber.in","r",stdin);
	freopen("kthnumber.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	build(1,n,1);
	while(m--){
		scanf("%d%d%d",&s,&t,&k);
		l=-(int)(1e9+0.5);r=-l;
		while(l<=r){
			ans=(l+r)>>1;
			tmp=0;
			query(1,n,1);
			if(tmp<k)l=ans+1;
			else r=ans-1;
		}
		printf("%d\n",r);
	}
#ifndef MINE
	printf("\n--------------------DONE--------------------\n");
	for(;;);
#else
	fclose(stdin);
	fclose(stdout);
#endif
	return 0;
}
void build(int l,int r,int rt){
	if(l==r){
		int x;
		scanf("%d",&x);
		insert(new node(x),rt);
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,rt<<1);
	build(mid+1,r,rt<<1|1);
	copy(rt,root[rt<<1]);
	copy(rt,root[rt<<1|1]);
}
void query(int l,int r,int rt){
	if(s<=l&&t>=r){
		tmp+=rank(ans,rt);
		return;
	}
	int mid=(l+r)>>1;
	if(s<=mid)query(l,mid,rt<<1);
	if(t>mid)query(mid+1,r,rt<<1|1);
}
void copy(int rt,node *x){
	if(!x)return;
	insert(new node(x->data),rt);
	copy(rt,x->lc);
	copy(rt,x->rc);
}
void insert(node *x,int i){
	if(!root[i]){
		root[i]=x;
		return;
	}
	node *rt=root[i];
	for(;;){
		if(x->data<rt->data){
			if(rt->lc)rt=rt->lc;
			else{
				rt->lc=x;
				break;
			}
		}
		else{
			if(rt->rc)rt=rt->rc;
			else{
				rt->rc=x;
				break;
			}
		}
	}
	x->prt=rt;
	while(rt){
		rt->refresh();
		rt=rt->prt;
	}
	splay(x,NULL,i);
}
int rank(int x,int i){
	node *rt=root[i],*y=rt;
	int ans=0;
	while(rt){
		y=rt;
		if(x<=rt->data)rt=rt->lc;
		else{
			if(rt->lc)ans+=rt->lc->size;
			ans++;
			rt=rt->rc;
		}
	}
	splay(y,NULL,i);
	return ans;
}
void splay(node *x,node *tar,int i){
	if(!x)return;
	for(node *rt=x->prt;rt!=tar;rt=x->prt){
		if(rt->prt==tar){
			if(x==rt->lc)rrot(rt,i);
			else lrot(rt,i);
			break;
		}
		if(rt==rt->prt->lc){
			if(x==rt->lc)rrot(rt,i);
			else lrot(rt,i);
			rrot(x->prt,i);
		}
		else{
			if(x==rt->rc)lrot(rt,i);
			else rrot(rt,i);
			lrot(x->prt,i);
		}
	}
}
void lrot(node *x,int i){
	node *y=x->rc;
	if(x->prt){
		if(x==x->prt->lc)x->prt->lc=y;
		else x->prt->rc=y;
	}
	else root[i]=y;
	y->prt=x->prt;
	x->rc=y->lc;
	if(y->lc)y->lc->prt=x;
	y->lc=x;
	x->prt=y;
	x->refresh();
	y->refresh();
}
void rrot(node *x,int i){
	node *y=x->lc;
	if(x->prt){
		if(x==x->prt->lc)x->prt->lc=y;
		else x->prt->rc=y;
	}
	else root[i]=y;
	y->prt=x->prt;
	x->lc=y->rc;
	if(y->rc)y->rc->prt=x;
	y->rc=x;
	x->prt=y;
	x->refresh();
	y->refresh();
}