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$，回答以下问题：

记 $X$ 为在 $A_1,A_2,\dots,A_N$ 中与点 $B_j$ 第 $k_j$ 近的点。求点 $X$ 与 $B_j$ 之间的距离。 更形式化地，令 $d_i$ 为点 $A_i$ 与 $B_j$ 之间的距离。将 $(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$ 行 $(1 \leq l \leq Q)$ 应包含对 $j=l$ 的问题的答案，作为一个整数。

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

7
3
13

2 2
0 0
0 1
0 2

0
0

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

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$ 所有输入值均为整数。下面解释第一个查询。 点 $A_1, A_2, A_3, A_4$ 到点 $B_1$ 的距离分别为 $1, 1, 7, 8$，因此与点 $B_1$ 第 3 近的是点 $A_3$。 因此，输出点 $A_3$ 与点 $B_1$ 之间的距离，即 $7$。
可能存在坐标相同的多个点。

标签: AtCoder|abc364D

来源

AtCoder|abc364D