测评记录

#include<bits/stdc++.h>
using namespace std;
struct kkk{
	int val,lc,rc;
}sgt[80000010];
int a[1000010],b[1000010],ha[1000010],tot,Hash[1000010],T[1000010];
int build(int begin,int end){
	if(begin == end){
		tot++;
		return tot;
	}
	tot++;
	int u = tot;
	int mid = (begin+end)/2;
	sgt[u].lc = build(begin,mid);
	sgt[u].rc = build(mid+1,end);
	
	return u;
}
int ins(int now,int b,int e,int x){
//	cout<<now<<endl;
	if(b == e){
		tot++;
		sgt[tot].val = sgt[now].val+1; 
		return tot;
	}
	int mid = (b+e)/2;
	int u = ++tot;
	sgt[u].val = sgt[now].val;
	sgt[u].val++;
	if(x <= mid){
		sgt[u].lc = ins(sgt[now].lc,b,mid,x);
		sgt[u].rc = sgt[now].rc;
	}
	else{
	    sgt[u].lc = sgt[now].lc;
		sgt[u].rc = ins(sgt[now].rc,mid+1,e,x);	
	}
	return u;
}
int gets(int u,int v,int l,int r,int k){
	if(l == r)return l;
	int mid = (l+r)/2;
	int x = sgt[sgt[v].lc].val-sgt[sgt[u].lc].val;
	if(x >= k){
		return gets(sgt[u].lc,sgt[v].lc,l,mid,k);
	}
	else{
		return gets(sgt[u].rc,sgt[v].rc,mid+1,r,k-x);
	}
}
bool pd[1000010];
int cnt = 0;
int main(){
	int n,m;
	cin>>n>>m;
	T[0] = 1;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		b[i] = a[i];
	}
	sort(a+1,a+1+n);
//	int size = unique(a+1,a+1+n)-a-1;
	
	build(1,n);
	for(int i = 1;i <= n;i++){
		if(a[i]!=a[i-1]){
		cnt++;
		Hash[a[i]] = cnt; 
		ha[cnt] = a[i];
	    }
	}
	for(int i = 1;i <= n;i++){
		T[i] = ins(T[i-1],1,n,Hash[b[i]]);
	}
	while(m--){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<ha[gets(T[l-1],T[r],1,n,k)]<<endl;
	} 
	return 0;
}