[模板]可持久化线段树

# 可持久化线段树-主席树 ```cpp #include <bits/stdc++.h> using namespace std; const int maxn = 200010; int n,q; namespace ZXTree{ int totID = 0; int L[maxn << 5],R[maxn << 5],sumv[maxn << 5]; int build(int l,int r){ int id = ++totID; int mid = l + r >> 1; if(l != r){ L[id] = build(l,mid); R[id] = build(mid+1,r); } return id; } int update(int preID,int l,int r,int x,int v){ int id = ++totID; int mid = l + r >> 1; L[id] = L[preID],R[id] = R[preID],sumv[id] = sumv[preID] + v; if(l != r){ if(x <= mid) L[id] = update(L[id],l,mid,x,v); else R[id] = update(R[id],mid+1,r,x,v); } return id; } int query(int u,int v,int l,int r,int k){ if(l == r) return l; int mid = l + r >> 1; int lcnt = sumv[L[v]] - sumv[L[u]]; if(lcnt >= k) return query(L[u],L[v],l,mid,k); else return query(R[u],R[v],mid+1,r,k-lcnt); } } int a[maxn],b[maxn],c[maxn]; int T[maxn]; int main(){ scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { scanf("%d",a+i); b[i] = a[i]; } sort(a+1,a+1+n); int m = unique(a+1,a+1+n) - a - 1; T[0] = ZXTree::build(1,m); for(int i=1;i<=n;i++) { c[i] = lower_bound(a+1,a+1+m,b[i]) - a; T[i] = ZXTree::update(T[i-1],1,m,c[i],1); } while(q--){ int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",a[ZXTree::query(T[l-1],T[r],1,m,k)]); } return 0; } ```