AT_abc364_d [ABC364D] K-th Nearest

题目描述

在数轴上有 $N+Q$ 个点，分别为 $A_1,\dots,A_N,B_1,\dots,B_Q$，其中点 $A_i$ 的坐标为 $a_i$，点 $B_j$ 的坐标为 $b_j$。

对于每个 $j=1,2,\dots,Q$，请回答以下问题：

• 在点 $A_1,A_2,\dots,A_N$ 中，与点 $B_j$ 的距离第 $k_j$ 近的点记为 $X$，请你求出点 $X$ 与点 $B_j$ 的距离。更严格地说，设点 $A_i$ 与点 $B_j$ 的距离为 $d_i$，将 $(d_1,d_2,\dots,d_N)$ 按升序排列后得到 $(d_1',d_2',\dots,d_N')$，请输出 $d_{k_j}'$。

输入格式

输入以如下格式从标准输入读入。

$N$ $Q$ $a_1$ $a_2$ $\dots$ $a_N$ $b_1$ $k_1$ $b_2$ $k_2$ $\vdots$ $b_Q$ $k_Q$

输出格式

请输出 $Q$ 行。第 $l$ 行输出当 $j=l$ 时问题的答案，输出为一个整数。

输入输出样例 #1

输入 #1

4 3
-3 -1 5 6
-2 3
2 1
10 4

输出 #1

7
3
13

输入输出样例 #2

输入 #2

2 2
0 0
0 1
0 2

输出 #2

0
0

输入输出样例 #3

输入 #3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

输出 #3

11
66
59
54
88

说明/提示

限制条件

• $1\leq N,Q \leq 10^5$
• $-10^8\leq a_i,b_j \leq 10^8$
• $1\leq k_j\leq N$
• 所有输入均为整数

样例解释 1

对于第 $1$ 个查询，点 $A_1,A_2,A_3,A_4$ 与点 $B_1$ 的距离依次为 $1,1,7,8$，因此与点 $B_1$ 的距离第 $3$ 近的是点 $A_3$。所以输出点 $A_3$ 与点 $B_1$ 的距离 $7$。

样例解释 2

同一坐标上可能存在多个点。

由 ChatGPT 4.1 翻译