Mnzn此生第二棵可持久化线段树求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005];
int b[1000005];
map<int,int>mp;
int R[1000005];
struct node{
	int val,ls,rs;
}tree[1000005<<2];
int tot;
inline int ls(int p){
	return tree[p].ls;
}
inline int rs(int p){
	return tree[p].rs;
}
inline void pushup(int p){
	tree[p].val=tree[ls(p)].val+tree[rs(p)].val;
}
inline void build(int p,int l,int r){
	if(l==r){
		tree[p].val=0;
//	if(l==r)return;
		return;
	}
	tree[p].ls=++tot;
	tree[p].rs=++tot;
//	cout<<p<<' '<<ls(p)<<" "<<rs(p)<<endl; 
//	if(l==r)return;
	int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
inline int update(int p,int l,int r,int chg,int k){
	if(l>=chg&&r<=chg){
		tree[++tot].val=k;
		return tot;
	}
	int mid=l+r>>1;
	tree[++tot]=tree[p];
	int t=tot;
	if(mid>=chg){
		tree[tot].ls=update(ls(p),l,mid,chg,k);
//		pushup(t);
	}
	else{
		tree[tot].rs=update(rs(p),mid+1,r,chg,k);
//		pushup(t);
	}
//	cout<<tree[tot].val<<" "<<tree[tot].ls<<" "<<tree[tot].rs<<endl;
	pushup(t);
	return t;
}
inline int query(int u,int v,int l,int r,int rk){
	if(l==r)return l;
	int mid=l+r>>1;
	if(tree[ls(v)].val-tree[ls(u)].val>=rk){
		return query(ls(u),ls(v),l,mid,rk);
	}
	else{
		return query(rs(u),rs(v),mid+1,r,rk);
	}
}
int root[1000005];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	int to=0;
	tot=1;
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++){
		if(!mp[b[i]]){
			mp[b[i]]=++to;
			R[to]=b[i];
		}
	}
	for(int i=1;i<=n;i++){
		a[i]=mp[a[i]];
	}
	build(1,1,n);
	root[0]=1;
//	cout<<tot<<endl;
	for(int i=1;i<=n;i++){
		root[i]=update(root[i-1],1,n,a[i],1);
	}
	while(m--){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<R[query(root[l-1],root[r],1,n,k)]<<endl;
	}
	return 0;
}