RT

不带修序列第k小

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int INF = 0x3fffffff;
const int N = 1e5 + 5;
struct Query {
	int k,id;
};
vector <Query> q;
int n,Q; 
int a[N],ans[N];
int check(int l,int x) {
	int res = 0;
	for(int i = 1;i <= n;i ++) if(a[i] >= l && a[i] <= x) res ++;
	return res;
}
void Solve(int l,int r,vector <Query> q) {
	int mid = (l + r) >> 1;
	if(l == r) {
		for(int i = 0;i < q.size();i ++) ans[q[i].id] = l;
		return ;
	}
	vector <Query> q1,q2;
	for(int i = 0;i < q.size();i ++) {
		if(check(l,mid) >= q[i].k) q1.push_back(q[i]);
		else {
			q[i].k -= check(l,mid);
			q2.push_back(q[i]);
		}
	}
	if(q1.size()) Solve(l,mid,q1);
	if(q2.size()) Solve(mid + 1,r,q2);
}
int main() {
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	scanf("%d%d",&n,&Q);
	for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
	for(int i = 1;i <= Q;i ++) {
		int k; scanf("%d",&k);
		q.push_back((Query){k,i});
	}
	Solve(1,INF,q);
	for(int i = 1;i <= Q;i ++) printf("%d ",ans[i]);
	puts("");
	return 0;
}