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

题目链接

Description

Input

Output

 

样例太长了,就不写了。

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

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

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

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

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

题解参考了iwtwiioi大爷的博客

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

 

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz