一看到第k小dna就动了，敲了个主席树板子，求助大佬

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int N=5000010;
vector<long long> v;
int n,k;
int a[N];
struct node{
	int l,r,sum;
}t[N*4];
int cnt,root[N];
inline int getid(int x){
	return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void insert(int l,int r,int pre,int &now,int p){
	t[++cnt]=t[pre];
	now=cnt;
	t[now].sum++;//新建数的权值+1
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) insert(l,mid,t[pre].l,t[now].l,p);
	else insert(mid+1,r,t[pre].r,t[now].r,p); 
}
int query(int l,int r,int L,int R,int k){
//L表示l-1那个那个版本的线段树遍历的当前节点 
//R表示R那个版本的权值线段树遍历的当前节点
	if(l==r) return l;
	int mid=(l+r)>>1;
	int tmp=t[t[R].l].sum-t[t[L].l].sum;//当前树上左子树的数个个数 
	if(k<=tmp){
		query(l,mid,t[L].l,t[R].l,k);
	}else{
		query(mid+1,r,t[L].r,t[R].r,k-tmp);
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		v.push_back(a[i]);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	
	for(int i=1;i<=n;i++){
		insert(1,n,root[i-1],root[i],getid(a[i]));
	}
	int m=1;
	while(m--){
		int l=1,r=n;
		printf("%d",v[query(l,r,root[l-1],root[r],k+1)]-1);//离散化回来输出 
	}
	return 0;
}