BZOJ 2648: SJY摆棋子&2716: [Violet 3]天使玩偶 K-Dtree

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
学习了一下K-Dtree,现在也只是学了个大概,简单说一下。。。如果有什么错误请尽情指出。
K-Dtree就是在k个维度这样一个空间上的一个划分,每个节点可以视为代表了一个矩形区域(在二维平面上来说)。它是一棵二叉树,而且类似于BST。毕竟如果k=1的时候,就相当于在数轴的一个划分,就是一棵BST了。
一般应用在二维平面上,比如这道题目就是在二维平面上找到一个点的最近点。
但是在二维或者更高维度上构建k-dtree的时候有一个问题,就是BST需要有一个比较,但是k个维度该怎么比较呢?有很多种方法,最简单的一种就是按照这k个维度的顺序进行轮流划分,比如对于二维平面,我们先按照x来划分这一层,找到一个根节点满足,他左儿子所代表的的矩形区域中的点都小于他的x坐标,右儿子所代表的矩形区域中的点都大于他的x坐标。这样的话每一次划分,都可以水平或者竖直的方向上把一个区域分成不相交的两部分,这样递归下去直到无法构建为止。
这样我们就知道了建树的方法,而节点信息我们主要维护的就是这个节点的x和y坐标,以及以他为根所代表的的这个矩形区域内,在x和y坐标的意义下的最大值和最小值。也就是说他所代表的那个矩形的边界信息。
当然我们可能需要维护一个Size域,因为我们可能需要动态的插入一些节点到k-dtree中,插入方式类比BST。但是这样有一个后果就是会导致k-dtree不再平衡。有一个简单的方法,就是替罪羊重构一下,来保证整棵树的平衡。
询问最近点的方式:维护一个全局变量ans,并初始为无穷大。我们先用当前根节点的信息来更新一下答案。然后拿(x,y)和根节点的左右儿子所代表的的矩形区域的边界进行比较,然后按照顺序,如果可以更优的话就更新递归下去,否则就退出。其实就是个暴力的剪枝。。。。
这样的复杂度在随机数据下是log的,但是如果构造的话是O(n)的。因为你本质上还是暴力嘛?什么数据?给你一个圆查圆心。。。。
网上很多人说是sqrt(n)其实是不对,k-dtree对于不同的询问信息复杂度不同,sqrt(n)貌似是剖矩形。。。
其实看看代码的话更好理解,了解了以上内容,那这两个题目就是裸题了。双倍经验撒花~~~

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注