论一类平面点对曼哈顿距离问题.ppt

1、a,1,一类平面点对曼哈顿距离问题的探究,常州市第一中学陈 子 旸,a,2,曼哈顿距离问题在信息学竞赛题目中十分常见 曼哈顿距离的定义：在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和 讨论将围绕一类平面上最大、最小曼哈顿距离点对问题展开,a,3,目录,引例 情况一：离线查询、无修改 情况二：在线查询、修改 情况三：在线查询、无修改 其他方法的讨论 总结,a,4,引例,(magic)题目大意：在一个(k=7)维的空间中，有(n=100000)个点，要求求出在这些点对中曼哈顿距离最远的点对之间的曼哈顿距离。,a,5,例题分析,直接暴力枚举点对？,显然TLE！,两点间曼哈顿

2、距离的计算公式：,以平面为例,a,6,例题分析,怎么处理？,分类讨论？,！完全不需要！,|x|+|y|=|x+y|,也就是说： 如果我们计算时如果不满足条件，所计算出的值会比真实值小，不会更新答案！,a,7,例题分析,处理时，只需要分别统计|(x1+y1)-(x2+y2)|的最大值和|(x1-y1)-(x2-y2)|的最大值，最后再取大的作答案就行了。,高维推广处理方法类似，以三维为例，只要统计x+y+z,x+y-z,x-y+z,x-y-z四类情况的答案就可以了。,a,8,通过引例，我们初步了解了这类问题的特点，同时发现了解决这类问题的一个重要的思想：去绝对值 在引例中，运用了求最大值的条件和

3、一个绝对值不等式，避免了分类讨论。但实际运用时往往要求最小值，我们不得不分类讨论解决这类问题，接下来的部分按题目的不同要求分析了几类不同情况。,a,9,情况一：离线查询，无修改,例题2(DONUT) 题目大意：在一个平面上有两类点，。对于每个类点求出离他曼哈顿距离最近的A类点与它的曼哈顿距离，其中类和类点的个数都不超过50000个，点的坐标范围在长整数范围内。,a,10,例题2分析,能不能套用例题1（magic）的方法？,糟糕！要求最小值,|x|+|y|=|x+y|,a,11,例题2分析,a,12,例题2分析,有点像二维RMQ问题？！,树套树？,二维ST？,可以离线处理!,a,13,例题2分析

4、,把所有点按照x的值排序，依次插入处理 处理一个点时，所有插入的点的x的值都小于当前点，所以只需要满足y的条件就可以了 处理对y的限制，只需要维护一棵维护x+y最大值的线段树，能够支持单点插入和区间查询最值两个操作就可以了,a,14,情况二：在线查询、带修改,例题3(DONUTEXT) 在一个平面上给定一个点集，可以动态地插入或删除点集中的点，并询问离点集中某个点最近的点到该点的曼哈顿距离。点集的大小不超过100000。,a,15,例题3分析,在线，带修改。离线算法神马的不管用了,我们需要一个能同时处理两个维度有序性的数据结构,有没有想到区间第k大数问题？,a,16,例题3分析,在区间第k大数

5、问题中，需要同时维护数在原序列中的位置和数的大小两个序关系 在区间第k大数问题中，可以使用归并树这一结构 下面来看一下如何把归并树运用到本题中,a,17,例题3分析,把x的值作第一关键字（类比区间第k大数问题中数在原数组的位置），y的值作第二关键字（类比区间第k大数问题中数的值），建立归并树 所有x符合查询要求的点分布在归并树中的O(log2n)个区间内，在每个区间中，y有序，可以通过二分答案找到y符合要求的区间。 最后，只要把归并树的每个节点用线段树维护起来就可以了,a,18,例题3分析,于是我们在O(n log22 n)的时间复杂度 和O(n log2 n)的空间复杂度内解决了这个问题,a

6、,19,情况三：在线查询，无修改,例题4(DONUTEXT2) 题目大意：在一个平面上给定一个点集，查询距离点（x，y）最近的点离它的曼哈顿距离，这里的x，y由上两问的答案经过某种变化得到。,a,20,例题4分析,从题面分析，这题似乎比上一题目要简单，因为没有修改操作,若果直接套用上一题的做法，那这题就没有存在的意义了,所以一定有效率更高的算法！,如何超越n log22 n?,我们想到了求解区间第k大数的又一神器,划分树,a,21,例题4分析,直观地理解划分树，就是把快排的过程建成一棵树,注意：划分树中每个数要维护：该节点中，在这个数之前被分到左子区间的数的个数，例如对于根结点中的7，这个值就

7、是3,a,22,例题4分析,划分树有很好的性质： 根结点记录原序列 下一层中被划分成的两个区间中的数字的相对顺序与上一层相同 从一个节点划分出的左子节点中的元素小于右子节点中的元素,这些性质可以帮助我们解决例题4,a,23,例题4分析,仍然以x为第一关键字，以y为第二关键字，建立划分树。这样，对于一次查询中x符合要求的点都在根结点从最左端开始的一段连续区间内。 这个区间内地的点被按y的大小分配在两个子区间中。依靠维护的额外信息，我们能O(1)地查出这两个子区间具体的边界。 如果左子区间的点最大的y大于查询的点，直接递归查询左子区间即可。,a,24,例题4分析,对于左子区间最大的y小于等于查询点

8、的情况： 查询区间被分到左子区间的部分一是一个从左子区间最左端开始的连续区间。通过欲处理部分最大值数组可以O(1)地完成对这部分点的询问。 对于被分到右子区间的部分，递归查询即可。 这样，我们在每层处理的时间复杂度是O(1)，由于划分树只有log 2n层，对于一次询问，我们的复杂度只有O(log 2n)，比例题3的方法更优秀。,a,25,例题4分析,13475,134,75,5,7,a,26,其他方法的讨论,当然，在处理这类问题的时候还有其他方法,四分树,可持久化数据结构（线段树）,树套树,a,27,四分树在这类题中的运用,回归问题本质：二维RMQ查询,一维线段树的拓展：四分树,a,28,一个

9、矛盾：,四分树在这类题中的运用,巨大的空间开销如何解决？,只把有用的节点建立起来！,a,29,可持久化数据结构在这类问题中的运用,概念：可持久化数据结构是一种特殊的数据结构的实现方式。 在可持久化数据结构中，元素一旦建立不能修改和删除。 每次修改操作，通过建立新的元素和重利用过去已经建立的元素实现。从而达到了保留数据结构的所有时刻版本的目的。,a,30,可持久化线段树简介,存储结构：指针实现。记录：左、右边界，左、右孩子，以及其他要维护的信息 建树：调用建树过程，返回建好的树的根节点 查询：直接查询对应历史版本的根结点，查询过程与普通线段树几乎一样,a,31,可持久化线段树简介,修改操作（核心

10、） ：修改操作返回一个新的根结点。对一个节点修改操作包括了递归修改和更新该节点信息两个过程。更新节点信息时，我们建立一个新的节点，新节点没有修改过的子节点设置为上一个历史版本的线段树中的节点，修改过的子节点设置为对应递归函数返回的节点 标记：同样可以实现，与本文关系不大,a,32,可持久化线段树简介,a,33,在本题中的具体运用,以分析在一个点左下的点为例，我们可以按照y坐标的顺序建立一个维护x+y最大值的线段树。并以x坐标的顺序依次插入节点，这样我们就可以得到按照x坐标插入的线段树的各个历史版本，通过类似离线问题的处理方法，解决所有询问，时空复杂度均为n log2 n。 是划分树的一种完美替代品。但对于点的修改会涉及到同时修改多个历史版本的线段树，情况复杂，这里不详细阐述。,a,34,总结,本文由一道简单的例题出发，着重分析了一类有关平面上点对的曼哈顿距离的问题。全文贯穿了去绝对值的思