Kd-Tree

Description # 这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

题目链接 # Description # Ayu 在二维平面上收集天使玩偶。初始时平面上有 \( N \) 个玩偶，坐标已知。接下来有 \( M \) 个操作： 发现一个新玩偶，坐标为 \( (x, y) \)。 Ayu 瞬移到了 \( (x, y) \)，需要寻找离当前位置最近的玩偶（曼哈顿距离最小），并输出该最小距离：\( \min_i (|x - x_i| + |y - y_i|) \). Input # 第一行两个整数 \( N, M \)（\( 1 \le N, M \le 5 \times 10^5 \)）。 接下来 \( N \) 行，每行两个整数 \( x_i, y_i \)，表示初始玩偶的坐标。 接下来 \( M \) 行，每行三个整数 \( t, x, y \)：

题目链接 题意： # 给出若干个点，在给出一个定点，求距离该定点最近的m个点。 思路： # 我们已经知道kd-tree可以得到最近邻，实际上M近邻，只需要维护一个size为M的优先队列就可以了。

题目链接 题意： # 有若干个(2E5)旅馆，分别给出旅馆的坐标和价格。有m个查询，每个查询给出一个人的位置(x0,y0)，以及其能接受的最高价格。问在该人能接受的价格内，距离其最近的旅馆的坐标和价格是多少。

题目链接：hdu2966 题意： # 给出二维平面上n(1E5)个点，问对于每个点，其他距离其最近的点的距离是多少。 思路： # kd-tree 裸题。

老规矩，资料先行。 好久没学新算法了，有点忘记怎么学了orz K-D tree 数据结构 hdu 2966 In case of failure　（k-d树　最近邻近点） 首先来看算法的提出。 现在二维平面上有n个点，知道这n个点的坐标，然后再添加一个点，问n个点中，距离新添加的点距离最近的点。