萌新刚学OI 1msP3834WA+RE求助0pt

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int root[N],a[N],b[N],c[N];
int sz[N<<5],lt[N<<5],rt[N<<5];
int tot;
int copy(int x)
{
	++tot;
	sz[tot]=sz[x];
	lt[tot]=lt[x];
	rt[tot]=rt[x];
	return tot;
}
int build(int pl,int pr)
{
	int p=++tot;
	if(pl==pr)
		return p;
	int mid=(pl+pr)>>1;
	lt[p]=build(lt[p],pl,mid);
	rt[p]=build(rt[p],mid+1,pr);
	return p;
}
int update(int p,int pl,int pr,int x)
{
	p=copy(p);
	++sz[p];
	if(pl==pr)
		return p;
	int mid=(pl+pr)>>1;
	lt[p]=update(lt[p],pl,mid,x);
	rt[p]=update(rt[p],mid+1,pr,x);
	return p;
}
int query(int u,int v,int pl,int pr,int k)
{
	if(pl==pr)
		return pl;
	int mid=(pl+pr)>>1,x=sz[lt[v]]-sz[lt[u]];
	if(k<=x)
		return query(lt[u],lt[v],pl,mid,k);
	return query(rt[u],rt[v],mid+1,pr,k-x);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i)
		cin>>a[i],b[i]=a[i];
	sort(b+1,b+n+1);
	int K=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;++i)
		a[i]=lower_bound(b+1,b+K+1,a[i])-b;
	root[0]=build(1,1,K);
	for(int i=1;i<=n;++i)
		root[i]=update(root[i-1],1,K,a[i]);
	while(m--)
	{
		int l,r,k;
		cin>>l>>r>>k;
		cout<<b[query(root[l-1],root[r],1,K,k)]<<'\n';
	}
}