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

区间第k大/小问题

洛谷P3834
好吧，区间问题，考虑线段树

でも,线段树能求解的问题须是大问题的解可以从小问题的解合并而来，显然，第k大/小问题不满足，不能直接用一颗树解决

考虑用多颗树
怎么想到的？我要是想到了我就成主席了
首先，烧烤一下如何用线段树求 1-i 的第 k 小值
烧烤ing……

以元素值为下标建树，线段树的点权表示这个区间有几个元素，查询，若当前节点的左儿子的点权 < k,则第 k 大的数在右儿子的区间里 ，> 则在左儿子里

就完了

更新ing

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005;
ll n,m,a[N],b[N],cnt;
ll root[N];
struct node{
	ll L,R,sum;
}tree[N<<5];
ll update(ll pre,ll pl,ll pr,ll x){
	ll rt=++cnt;
	tree[rt].L=tree[pre].L;
	tree[rt].R=tree[pre].R;
	tree[rt].sum=tree[pre].sum+1;
	ll mid=(pl+pr)>>1;
	if(pl<pr){
		if(x<=mid)
			tree[rt].L=update(tree[pre].L,pl,mid,x);
		if(x>mid)
			tree[rt].R=update(tree[pre].R,mid+1,pr,x);
	}
	return rt;
}
ll query(ll u,ll v,ll pl,ll pr,ll k){
	if(pl==pr)return pl;
	ll x=tree[tree[v].L].sum-tree[tree[u].L].sum;
	ll mid=(pl+pr)>>1;
	if(x>=k)return query(tree[u].L,tree[v].L,pl,mid,k);
	if(x<k)return query(tree[u].R,tree[v].R,mid+1,pr,k-x);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	ll size=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++){
		ll x=lower_bound(b+1,b+1+size,a[i])-b;
		root[i]=update(root[i-1],1,size,x);
	}
	for(int i=1;i<=m;i++){
		ll x,y,k;
		cin>>x>>y>>k;
		ll t=query(root[x-1],root[y],1,size,k);
		cout<<b[t]<<endl;
	}
	return 0;
}