可持久化线段树-主席树

求第k小数

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1e4+10;
vector<int>nums;
int n,m;
int a[N];
int root[N];
int idx;

struct tree
{
	int l,r;
	int cnt;
}t[N*21];


int find(int x)
{
	return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}

int build(int l,int r)
{
	int p=++idx;
	if(l==r) return p;
	int mid=(l+r)>>1;
	t[p].l=build(l,mid),t[p].r=build(mid+1,r);
	return p;
}

int insert(int p,int l,int r,int x)
{
	int q=++idx;
	t[q]=t[p];
	if(l==r)
	{
		t[q].cnt++;
		return q;
	}
	int mid=(l+r)>>1;
	if(x<=mid) t[q].l=insert(t[p].l,l,mid,x);
	else t[q].r=insert(t[p].r,mid+1,r,x);
	t[q].cnt=t[t[q].l].cnt+t[t[q].r].cnt;
	return q;
}

int query(int p,int q,int l,int r,int k)
{
	if(l==r) return r;
	int cnt=t[t[q].l].cnt-t[t[p].l].cnt;
	int mid=(l+r)>>1;
	if(k<=cnt) return query(t[p].l,t[q].l,l,mid,k);
	else return query(t[p].r,t[q].r,mid+1,r,k-cnt);
}

int main(){
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i],nums.push_back(a[i]);
	sort(nums.begin(),nums.end());
	nums.erase(unique(nums.begin(),nums.end()),nums.end());
	
	root[0]=build(0,nums.size()-1);
	
	for(int i=1;i<=n;i++)
	{
		root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));
	}
	
	while(m--)
	{
		int l,r,k;
		cin>>l>>r>>k;
		printf("%d\n",nums[query(root[l-1],root[r],0,nums.size()-1,k)]);
	}
	
	return 0;
}