2*MLE求条 主席树

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=300005;
int asort[maxn],cnt=0;
int arr[maxn],s=0;
int lft[maxn*25];
int rit[maxn*25];
int root[maxn];
int size[maxn*25];
int build(int l,int r)
{
	cnt++;
	int rt=cnt;
	if(l<r)
	{
		int mid=(l+r)>>1;
		lft[rt]=build(l,mid);
		rit[rt]=build(mid+1,r);
	}	
	return rt;
}
int insert(int x,int l,int r,int id)
{
	cnt++;int rt=cnt;
	lft[rt]=lft[id];rit[rt]=rit[id];
	size[rt]=size[id]+1;
	if(l<r)
	{
		int mid=(l+r)>>1;
		if(x<=mid)
		{
			lft[rt]=insert(x,l,mid,lft[rt]);
		}	
		else
		{
			rit[rt]=insert(x,mid+1,r,rit[rt]);
		}
	}
	return rt;
}
int query(int x,int l,int r,int u,int v)
{
	if(l==r)
	{
		return l;
	}
	int sz=size[lft[v]]-size[lft[u]];
	int mid=(l+r)>>1;
	if(sz>=x)
	{
		return query(x,l,mid,lft[u],lft[v]);
	}
	else
	{
		return query(x-sz,mid+1,r,rit[u],rit[v]);
	}
}
signed main()
{
	cin.tie(0);cout.tie(0);
	int n,m;
	cin>>n>>m;
	asort[0]=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>arr[i];
		if(asort[s]!=arr[i])
		{
			s++;
			asort[s]=arr[i];
		}
	}
	sort(asort+1,asort+s+1);
	for(int i=1;i<=n;i++)
	{
		arr[i]=lower_bound(asort+1,asort+1+n,arr[i])-asort;
	}
	root[0]=build(1,n);
	for(int i=1;i<=n;i++)
	{
		root[i]=insert(arr[i],1,n,root[i-1]);
	}
	while(m--)
	{
		int l,r,x;
		cin>>l>>r>>x;
		cout<<asort[query(x,1,n,root[l-1],root[r])]<<"\n";
	}
	return 0;
}