KNN算法

题目描述

K最邻近（KNN，K-NearestNeighbor）分类算法是数据挖掘分类技术中最简单的方法之一。

Orange最近迷上了KNN算法，他向你提出了如下问题：

在一维空间中有点集 $S$ 包含 $n$ 个点，请快速回答如下 $q$ 次询问：

• 第 $i$ 次查询给出点 $p_i$ 和整数 $k_i$，要求输出 $S$ 中与点 $p_i$ 距离第 $k_i$ 近的点和 $p_i$的距离。

距离的定义：若点 $u_i$ 坐标为 $x_i$，$v_i$ 坐标为 $y_i$，则定义点 $u_i$ 与点 $v_i$ 的距离为 $|x_i-y_i|$ 。

输入格式

第一行两个整数 $n,q$ $(1\le n, q \le 2 \times 10^5)$ 表示点集 $S$ 的大小和查询次数。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ $(-10^9 \le a_i \le 10^9)$ 描述点集 $S$ 里第 $i$ 个点的坐标。

保证对于 $\forall i, j$ $(1\le i \lt j \le n)$ 有 $a_i \neq a_j$ 。

接下来 $q$ 行， 第 $i$ 行两个整数 $x_i,k_i$ $(-10^9 \le x_i \le 10^9, \ 1\le k_i \le n)$，表示 $p_i$ 的坐标和需要查询距离 $p_i$ 第 $k_i$ 近的结果。

输出格式

输出 $q$ 行，第 $i$ 行一个整数，表示第 $i$ 次查询的答案。

样例 #1

样例输入 #1

5 3
10 -2 1 3 4
12 4
3 1
2 2

样例输出 #1

11
0
1