K-th Number

PKU 2761

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;


struct Node{
	Node*left,*right;
	int key,value,sum; // sum:左側の数の合計
};

Node pool[100001*20];
int nodecnt=-1;

Node root;
Node* roots[100001];

int N,Q,k;
int a[100001],b[100001];

// 探索木に値を追加する

void add_node(Node *node,int key,int value){
	if(node->key==key)return;
	if(key<node->key){
		if(node->left){
			add_node(node->left,key,value);
		}else{
			Node& tar=pool[nodecnt++];
			tar.key=key;tar.value=value;
			tar.left=tar.right=0;
			tar.sum=0;
			node->left=&tar;
		}
	}else{
		if(node->right){
			add_node(node->right,key,value);
		}else{
			Node& tar=pool[nodecnt++];
			tar.key=key;tar.value=value;
			tar.left=tar.right=0;
			tar.sum=0;
			node->right=&tar;
		}
	}
}
void add_node(int key,int value=0){
	if(nodecnt==-1){
		root.key=key;root.value=value;
		root.left=root.right=0;
		root.sum=0;
		nodecnt=0;
	}else{
		add_node(&root,key,value);
	}
}
void add_nodes(int l,int r){
	if(l>=r)return;
	int mid=(l+r)/2;
	add_node(b[(l+r)/2]);
	add_nodes(l,mid);
	add_nodes(mid+1,r);
}
Node *nrec[100];
Node *rec2[100];
enum{LEFT,RIGHT};
int move[100];
Node *add_value(Node*node,int key){
	int cnt=0;
	nrec[cnt++]=node;
	while(node->key!=key){
		if(key<node->key){
			node=node->left;
			move[cnt-1]=LEFT;
		}else{
			node=node->right;
			move[cnt-1]=RIGHT;
		}
		nrec[cnt++]=node;
	}
	int plus=1;
	for(int i=cnt-1;i>=0;i--){
		Node *tmp=nrec[i];
		Node& tar=pool[nodecnt++];
		tar.key=tmp->key;
		tar.value=tmp->value;
		tar.sum=tmp->sum;
		if(i==cnt-1)tar.value++;
		if(plus)tar.sum++;
		tar.left=tmp->left;
		tar.right=tmp->right;
		if(i<cnt-1){
			if(move[i]==RIGHT){
				tar.right=rec2[i+1];
			}else{
				tar.left=rec2[i+1];
			}
		}
		rec2[i]=&tar;
		if(i>0&&move[i-1]==RIGHT)plus=0; else plus=1;
	}

	return rec2[0];
}

int solve(Node *l,Node *r,int k){
	int cnt=r->sum-l->sum;
	if(k>=cnt){
		if(l->right==0){
			return -1;
		}
		return solve(l->right,r->right,k-cnt);
	}else{
		if(l->left==0)return l->key;
		int ret=solve(l->left,r->left,k);
		if(ret==-1){
			ret=l->key;
		}
		return ret;
	}
}
// [l,r)の中でk番目の要素を求める
int solve(int l,int r,int k){
	Node* rn=roots[r],* ln=roots[l];
	return solve(ln,rn,k);
}
int main() {
	scanf("%d%d",&N,&Q);
	for(int i=0;i<N;i++)scanf("%d",a+i);
	memcpy(b,a,sizeof(b));
	sort(b,b+N);
	k=unique(b,b+N)-b;
	add_nodes(0,k);
	// 永続木の作成
	roots[0]=&root;
	for(int i=0;i<N;i++){
		roots[i+1]=add_value(roots[i],a[i]);
	}
	int l,r,k;
	for(int i=0;i<Q;i++){
		scanf("%d%d%d",&l,&r,&k);
		printf("%d\n",solve(l-1,r,k-1));
	}
	return 0;
}