主席树

想明白原理的点：https://blog.csdn.net/ModestCoder_/article/details/90107874

列题：洛谷P3834

代码：

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define IOS std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
template<class T> inline void read(T &x){
    x=0; register char c=getchar(); register bool f=0;
    while(!isdigit(c))f^=c=='-',c=getchar();
    while(isdigit(c))x=x*10+c-'0',c=getchar(); if(f)x=-x;
}
using namespace std;
const int maxn=200005;
struct node
{
	int l,r,val;
}e[maxn*35];
int a[maxn],cnt,n,m;
int root[maxn];
vector<int> v;
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
void update(int l,int r,int &x,int y,int pos)
{
	e[++cnt]=e[y];
	e[cnt].val++;
	x=cnt;
	if(l==r){return;}
	int mid=(l+r)/2;
	if(pos<=mid){update(l,mid,e[x].l,e[y].l,pos);}
	else{update(mid+1,r,e[x].r,e[y].r,pos);}
}
int query(int l,int r,int x,int y,int k)
{
	if(l==r){return l;}
	int mid=(l+r)/2;
	int sum=e[e[y].l].val-e[e[x].l].val;
	if(k<=sum){return query(l,mid,e[x].l,e[y].l,k);}
	else{return query(mid+1,r,e[x].r,e[y].r,k-sum);}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		v.pb(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++)
	{
		update(1,n,root[i],root[i-1],getid(a[i]));
	}
	while(m--)
	{
		int l,r,k;
		scanf("%d %d %d",&l,&r,&k);
		printf("%d\n",v[query(1,n,root[l-1],root[r],k)-1]);
	}
	return 0;
}