BZOJ 2648: SJY摆棋子 (动态kd-tree,插入,曼哈顿距离,输入挂)

Description

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

Input

第一行两个数 N M
以后M行,每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output


1
2
其实就是BZOJ2716 的双倍经验题
写出来是因为,这道题要加输入挂才可以过orz

 

BZOJ 2716: [Violet 3]天使玩偶 (动态kd-tree,带插入,曼哈顿距离模板题)

题目链接

Description

Input

Output

 

样例太长了,就不写了。

题意是说,现在有n个在二维平面,m个操作,2种类型,一种是加入一个点,另一种是对于一个定点,询问距离其最近的点的距离。

动态kd-tree的模板题,带插入操作。

插入其实就是直接暴力插的。

需要注意的是,这道题的距离度量是曼哈顿距离,略麻烦。

对于每个点,我们需要维护四个方向的极值。也就是kd-tree中某个节点所代表的空间,能管到的上下左右的最大(最小)坐标。

题解参考了iwtwiioi大爷的博客

代码风格参考了【bzoj 2716】[Violet 3]天使玩偶a  

 

 

 

 

hdu 4347 The Closest M Points (kd-tree+优先队列,求M近邻)

题目链接

题意:

给出若干个点,在给出一个定点,求距离该定点最近的m个点。

思路:

我们已经知道kd-tree可以得到最近邻,实际上M近邻,只需要维护一个size为M的优先队列就可以了。

需要注意,优先队列的元素一定要先定义小于关系orz

以及这次采用了轮盘转的策略划分维度,也就是按照深度,所有维度轮流作为split-method(实际用起来效果还是挺棒的orz

 

 

hdu 5992 Finding Hotels (kd-tree 裸题,查询)

题目链接

题意:

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

思路:

kd-tree学习笔记

加了价格的限制其实无所谓,只要在更新的时候,先判一下价格就行了。

训练的时候不会kd-tree。。感觉有点可惜了。不然就6题了orz

 

 

 

hdu 2966 In case of failure ( kd-tree(只有查询) 模板题)

题目链接:hdu2966  

题意:

给出二维平面上n(1E5)个点,问对于每个点,其他距离其最近的点的距离是多少。

思路:

kd-tree 裸题。

kd-tree 学习笔记

 

kd tree 学习笔记

老规矩,资料先行。

好久没学新算法了,有点忘记怎么学了orz

K-D tree 数据结构

hdu 2966 In case of failure (k-d树 最近邻近点)

 

首先来看算法的提出。

现在二维平面上有n个点,知道这n个点的坐标,然后再添加一个点,问n个点中,距离新添加的点距离最近的点。

如果不做任何预处理,那么就是暴力枚举每个点,与该定点的距离。

如何优化呢? 我们可以考虑把点域均等划分成若干个方块。

这样每次询问的时候只需要查询定点所在方格,以及定点相邻的8个方格中的点与该定点的距离即可。(除非这九个方格中没有点)

这种划分方法,对于随机数据大概是美滋滋,但是数据不会那么随机,因此划分也不能均等划 分。

这个时候, kd-tree 登场。k-d树( k-维的缩写)是在k欧几里德空间组织的数据结构

对于二维平面,kd-tree的思想是,提供一种平面的划分方法,使得对于任意输入数据,划分尽可能均匀。

划分方法其实不唯一,常用的划分方法是,对于k维中的每一维,按照方差最大的那一维划分。

(看到有些题解中,用该维度的极差(就是最大值-最小值)来作为度量,也就是按照极差最大的那一维度划分。)

(用方差的度量往往比较慢,看到根据二叉树的深度,交替维度也是一种常用做法 比如2016青岛 onsite)

下面是具体的划分过程。

 假设现在我们有平面上的点集 E ,其中有 5 个二维平面上的点 : (1,4)(5,8) (4,2) (7,9) (10,11)

        它们在平面上的分布如图:

                                                                

        首先,我们对区间 [ 1 , 5 ] 建树:

        先计算区间中所有点在第一维(也就是 x 坐标)上的方差:

                平均值 : ave_1 =5.4

                方差 : varance_1 =9.04

        再计算区间中所有点在第二维(也就是 y 坐标)上的方差:

                平均值:ave_2 =6.8

                方差:varance_2 =10.96

        明显看见,varance_2 > varance_1 ,那么我们在本次建树中,分裂方式 :split_method =2 , 再将所有的点按照 第 2 维 的大小从小到大排序,得到了新的点的一个排列:

                (4,2) (1,4)(5,8) (7,9) (10,11)

        取中间的点作为分裂点 sorted_mid =(5,8)作为根节点,再把区间 [ 1 , 2] 建成左子树 , [ 4 , 5] 建成右子树,此时,直线 : y = 8 将平面分裂成了两半,前面一半给左儿子,后面一半给了右儿子,如图:

                                                                

        建左子树 [1 , 3 ] 的时候可以发现,这时候是 第一维 的方差大 ,分裂方式就是1 ,把区间 [ 1, 2 ] 中的点按照 第一维 的大小,从小到大排序 ,取中间点(1,4) 根节点,再以区间 [ 2, 2] 建立右子树 得到节点 (4,2)

                                                                

         建右子树 [4 , 5 ] 的时候可以发现,这时还是 第一维 的方差大, 于是,我们便得到了这样的一颗二叉树 也就是 K-D tree,它把平面分成了如下的小平面,使得每个小平面中最多有一个点:

                                                                 

        可以看见,我们实际上在建树的过程中,把整个平面分成了 4 个部分

        树是建了,那么查询呢?

        查询过程:

                查询,其实相当于我们要将一个点“添加”到已经建好的 K-D tree 中,但并不是真的添加进去,只是找到他应该处于的子空间即可,所以查询就显得简单的毒攻了

                每次在一个区间中查询的时候,先看这个区间的分裂方式是什么,也就是说,先看这个区间是按照哪一维来分裂的,这样如果这个点对应的那一维上面的值比根节点的小,就在根节点的左子树上进行查询操作,如果是大的话,就在右子树上进查询操作

                每次回溯到了根节点(也就是说,对他的一个子树的查找已经完成了)的时候,判断一下,以该点为圆心,目前找到的最小距离为半径,看是否和分裂区间的那一维所构成的平面相交,要是相交的话,最近点可能还在另一个子树上,所以还要再查询另一个子树,同时,还要看能否用根节点到该点的距离来更新我们的最近距离。为什么是这样的,我们可以用一幅图来说明:

                                                                

         在查询到左儿子的时候,我们发现,现在最小的距离是 r = 10 ,当回溯到父亲节点的时候,我们发现,以目标点(10,1)为圆心,现在的最小距离 r = 10 为半径做圆,与分割平面 y = 8 相交,这时候,如果我们不在父亲节点的右儿子进行一次查找的话,就会漏掉 (10,9) 这个点,实际上,这个点才是距离目标点 (10,1) 最近的点

由于每次查询的时候可能会把左右两边的子树都查询完,所以,查询并不是简单的 log(n) 的,最坏的时候能够达到 sqrt(n)

 

放一份kd-tree的代码,按照上面讲解的过程(不是作为模板)

 

然后放一道例题:hdu2966