经典的数据结构。
权值线段树：
维护一个序列，然后记下每个 \(a_i\) 的出现次数，相当于线段树维护桶。
然后这样就可以轻而易举的求出 \(1-n\) 之间的第 \(k\) 小数了。原理类似于平衡数求 \(rank.\)
动态 · 可持久化
下面考虑动态的权值线段树。
\(l-r\) 查询可以理解为第 \(r\) 个线段树与 \(l-1\) 线段树的差（每个位置的差）的第 \(k\) 小数。
怎么做呢？只要建 \(n\) 个线段树就好了。但是这样的空间复杂度是 \(\mathcal{O(n^2\log n)}\) 的，不能被接受。
所以考虑新开点之后记录。
考虑到每一次加入都只会修改一条链上面的值，所以只新建那一条链上的至多 \(mathcal{O(\log n)}\) 的点不就好了。
程序
程式
#include <bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
using namespace std;
const int N=2e5+10;
int rt[N<<5],s[N<<5],ls[N<<5],rs[N<<5];
int a[N],b[N];
int cnt;
int build(int l,int r){
int u=++cnt;
if(l==r) return ls[u]=rs[u]=0,u;
ls[u]=build(l,mid), rs[u]=build(mid+1,r);
return u;
}
int add(int p,int l,int r,int x){
int u=++cnt;
s[u]=s[p]+1, ls[u]=ls[p], rs[u]=rs[p];
if(l==r) return u;
if(x<=mid) ls[u]=add(ls[p],l,mid,x);
else rs[u]=add(rs[p],mid+1,r,x);
return u;
}
int qry(int u,int v,int l,int r,int k){
if(l==r) return l;
int dlt=s[ls[u]]-s[ls[v]];
if(dlt>=k) return qry(ls[u],ls[v],l,mid,k);
else return qry(rs[u],rs[v],mid+1,r,k-dlt);
}
int n,m;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin>>n>>m;
build(1,n);
for(int i=1;i<=n;++i) cin>>b[i], a[i]=b[i];
stable_sort(b+1,b+n+1);
int len=unique(b+1,b+n+1)-b;
for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+len+1,a[i])-b;
for(int i=1;i<=n;++i) rt[i]=add(rt[i-1],1,n,a[i]);
while(m--){
int l,r,k; cin>>l>>r>>k;
cout<<b[qry(rt[r],rt[l-1],1,n,k)]<<"\n";
}
return 0;
}