这个东西有很多名字，主席树，可持久化线段树，函数式线段树。
我们用前缀和的思想，对每个前缀建线段树，区间表示数的大小，进行二分。
我在B站学算法：https://www.bilibili.com/video/av4619406/?from=search&seid=2734527038623001186#page=2
这个人讲的很不错，十分钟学代码超赚啊。
1 #include<bits.stdc++.h> 2 using namespace std; 3 const int N=1e5+10; 4 vector<int>v; 5 struct node 6 { 7 int l,r,s; 8 }t[N*40]; 9 int rt[N],a[N],cnt; 10 int get(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;} 11 void update(int l,int r,int x,int &y,int pos) 12 { 13 y=++cnt;t[y]=t[x];t[y].s++; 14 if(l==r)return; 15 int m=(l+r)>>1; 16 if(pos<=m)update(l,m,t[x].l,t[y].l,pos); 17 else update(m+1,r,t[x].r,t[y].r,pos); 18 } 19 int query(int l,int r,int x,int y,int num) 20 { 21 if(l==r)return l; 22 int sum=t[t[y].l].s-t[t[x].l].s; 23 int m=(l+r)>>1; 24 if(sum>=num)return query(l,m,t[x].l,t[y].l,num); 25 else return query(m+1,r,t[x].r,t[y].r,num-sum); 26 } 27 int main() 28 { 29 int n,m;int x,l,r; 30 scanf("%d%d",&n,&m); 31 for(int i=1;i<=n;++i)scanf("%d",&a[i]),v.push_back(a[i]); 32 sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end()); 33 for(int i=1;i<=n;++i)update(1,n,rt[i-1],rt[i],get(a[i])); 34 for(int i=1;i<=m;++i) 35 { 36 scanf("%d%d%d",&l,&r,&x); 37 printf("%d ",v[query(1,n,rt[l-1],rt[r],x)-1]); 38 } 39 return 0; 40 }