【bzoj2648】$SJY$摆棋子

题目大意

在一个很大的棋盘上，摆好了$n$个黑色棋子，现在执行$m$次操作，分为两种：

1. 摆一个黑色棋子

2. 摆一个白色棋子，同时输出距离这个棋子最近的一个黑色棋子与它的距离(曼哈顿距离)

值得注意的是，一个地方可以放两个棋子

数据范围

$n,m\leqslant 500000$

题解

对于这一个问题，有一个简单思路，每次新摆一个白色棋子然后枚举黑色棋子，计算曼哈顿距离

很好，但是$n$，$m$到了五十万[捂脸]

这时候我们引入一个东西，叫做$K-D\ Tree$

Tree？这是二维的图哦

嗯，实际上这是引入$K-D\ Tree$，而不是别的什么玄学结构的原因之一

这个$Tree$是这样建树的：

1. 选定一个维度

2. 针对每个点在这个维度上的参数$a_1,a_2,a_3..a_n$，用$STL$中的$nth\_element()$排序，使得在中间值左边的值全都比它小，右边的值全都比它大，但不保证有序

3. 把中间值取出，把这个点当成根节点

4. 选定另一个维度，递归左边的值(左平面)作为左子树，再递归右边的值(右平面)作为右子树

5. 递归完之后更新根节点记录的信息

当然如果只有一个维度，它的效率比别的数据结构较之一般，但是在多维度上，就显示出很强势的一面啦

对于这道题，插入和查询怎么办？

插入一个新的节点，只要针对某一维度上的参数与节点作比较，然后递归到子树即可

查询就需要节点记录的信息了

例如这道题，节点记录平面上极值点的坐标参数，然后比较对于查询位置来说哪个平面上的极值点更近，就递归哪个平面(子树)

关于其他的东西，我在代码旁做了比较详细的注释，那么这道题的题解就结束了！

阅读更多……