====== 主席树 ======

===== 例题 =====

[[https://www.luogu.com.cn/problem/P3834|洛谷 P3834 【模板】可持久化线段树 2（主席树）]]

参考代码：

<code cpp>
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int cnt;
int a[N],b[N],rt[N];
int tr[N<<5],ls[N<<5],rs[N<<5];
void build(int& o,int l,int r){
    o=++cnt;
    tr[o]=0;
    int mid=l+r>>1;
    if(l==r){
        return;
    }
    build(ls[o],l,mid);
    build(rs[o],mid+1,r);
}
void xg(int& o,int l,int r,int pre,int x){
    o=++cnt;
    ls[o]=ls[pre];
    rs[o]=rs[pre];
    tr[o]=tr[pre]+1;
    int mid=l+r>>1;
    if(l==r) return;
    if(x<=mid) xg(ls[o],l,mid,ls[pre],x);
    if(x>mid) xg(rs[o],mid+1,r,rs[pre],x);
}
int cx(int u,int v,int l,int r,int k){
    if(l>=r) return l;
    int x=tr[ls[v]]-tr[ls[u]];
    int mid=l+r>>1;
    if(x>=k) return cx(ls[u],ls[v],l,mid,k);
    else return cx(rs[u],rs[v],mid+1,r,k-x);
}
int main(){
    int n,q,m;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    m=unique(b+1,b+n+1)-b-1;
    build(rt[0],1,m);
    for(int i=1;i<=n;i++){
        int t=lower_bound(b+1,b+m+1,a[i])-b;
        xg(rt[i],1,m,rt[i-1],t);
    }
    while(q--){
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        int t=cx(rt[x-1],rt[y],1,m,z);
        printf("%d\n",b[t]);
    }
    return 0;
}
</code>