（可持久化线段树）主席树

上面就是我的丑图hh，一般主席树开40倍空间就可以了，每次插入的时候只需要比较前一个版本和这一个版本就行了，然后每个版本是区间可减的，比如询问l到r之间的第k大，只需要处理r-(l-1）版本的数量即可。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
struct node{
   
	int l;
	int r;
	int sum;
}tr[N*40];
int cnt;
int a[N];
int root[N];
vector<int>v;
int getid(int x)
{
   
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void insert(int l,int r,int pre,int &now,int p)
{
   
	tr[++cnt]=tr[pre];
	now=cnt;
	tr[now].sum++;
	if(l==r)
	return ;
	int mid=l+r>>1;
	if(p<=mid) insert(l,mid,tr[pre].l,tr[now].l,p);
	else insert(mid+1,r,tr[pre].r,tr[now].r,p);
}
int query(int l,int r,int L,int R,int k)
{
   
	if(l==r)
	return l;
	int tmp=tr[tr[R].l].sum-tr[tr[L].l].sum;
	int mid=l+r>>1;
	if(k<=tmp)
	return query(l,mid,tr[L].l,tr[R].l,k); 
	else
	return query(mid+1,r,tr[L].r,tr[R].r,k-tmp);
}
int main()
{
   
	int n,m;
	cin>>n >> m;
	for(int i=1;i<=n;i++)
	cin>>a[i],v.push_back(a[i]);
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++)
	insert(1,n,root[i-1],root[i],getid(a[i]));
	while(m--)
	{
   
		int l,r,k;
		cin>>l>>r>>k;
		cout<<v[query(1,n,root[l-1],root[r],k)-1]<<endl;
	}
}