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

一类平面点对曼哈顿距离问题的探究,常州市第一中学陈子旸,曼哈顿距离问题在信息学竞赛题目中十分常见曼哈顿距离的定义：在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和讨论将围绕一类平面上最大、最小曼哈顿距离点对问题展开,目录,引例情况一：离线查询、无修改情况二：在线查询、修改情况三：在线查询、无修改其他方法的讨论总结,引例,(magic)题目大意：在一个(k=|x+y|,例题2分析,例题2分析,有点像二维RMQ问题？！,树套树？,二维ST？,可以离线处理!,例题2分析,把所有点按照x的值排序，依次插入处理处理一个点时，所有插入的点的x的值都小于当前点，所以只需要满足y的条件就可以了处理对y的限制，只需要维护一棵维护x+y最大值的线段树，能够支持单点插入和区间查询最值两个操作就可以了,情况二：在线查询、带修改,例题3(DONUTEXT)在一个平面上给定一个点集，可以动态地插入或删除点集中的点，并询问离点集中某个点最近的点到该点的曼哈顿距离。点集的大小不超过100000。,例题3分析,在线，带修改。离线算法神马的不管用了,我们需要一个能同时处理两个维度有序性的数据结构,有没有想到区间第k大数问题？,例题3分析,在区间第k大数问题中，需要同时维护数在原序列中的位置和数的大小两个序关系在区间第k大数问题中，可以使用归并树这一结构下面来看一下如何把归并树运用到本题中,例题3分析,把x的值作第一关键字（类比区间第k大数问题中数在原数组的位置），y的值作第二关键字（类比区间第k大数问题中数的值），建立归并树所有x符合查询要求的点分布在归并树中的O(log2n)个区间内，在每个区间中，y有序，可以通过二分答案找到y符合要求的区间。最后，只要把归并树的每个节点用线段树维护起来就可以了,例题3分析,于是我们在O(nlog22n)的时间复杂度和O(nlog2n)的空间复杂度内解决了这个问题,情况三：在线查询，无修改,例题4(DONUTEXT2)题目大意：在一个平面上给定一个点集，查询距离点（x，y）最近的点离它的曼哈顿距离，这里的x，y由上两问的答案经过某种变化得到。,例题4分析,从题面分析，这题似乎比上一题目要简单，因为没有修改操作,若果直接套用上一题的做法，那这题就没有存在的意义了,所以一定有效率更高的算法！,如何超越nlog22n?,我们想到了求解区间第k大数的又一神器,划分树,例题4分析,直观地理解划分树，就是把快排的过程建成一棵树,注意：划分树中每个数要维护：该节点中，在这个数之前被分到左子区间的数的个数，例如对于根结点中的7，这个值就是3,例题4分析,划分树有很好的性质：根结点记录原序列下一层中被划分成的两个区间中的数字的相对顺序与上一层相同从一个节点划分出的左子节点中的元素小于右子节点中的元素,这些性质可以帮助我们解决例题4,例题4分析,仍然以x为第一关键字，以y为第二关键字，建立划分树。这样，对于一次查询中x符合要求的点都在根结点从最左端开始的一段连续区间内。这个区间内地的点被按y的大小分配在两个子区间中。依靠维护的额外信息，我们能O(1)地查出这两个子区间具体的边界。如果左子区间的点最大的y大于查询的点，直接递归查询左子区间即可。,例题4分析,对于左子区间最大的y小于等于查询点的情况：查询区间被分到左子区间的部分一是一个从左子区间最左端开始的连续区间。通过欲处理部分最大值数组可以O(1)地完成对这部分点的询问。对于被分到右子区间的部分，递归查询即可。这样，我们在每层处理的时间复杂度是O(1)，由于划分树只有log2n层，对于一次询问，我们的复杂度只有O(log2n)，比例题3的方法更优秀。,例题4分析,13475,134,75,5,7,其他方法的讨论,当然，在处理这类问题的时候还有其他方法,四分树,可持久化数据结构（线段树）,树套树,四分树在这类题中的运用,回归问题本质：二维RMQ查询,一维线段树的拓展：四分树,一个矛盾：,四分树在这类题中的运用,巨大的空间开销如何解决？,只把有用的节点建立起来！,可持久化数据结构在这类问题中的运用,概念：可持久化数据结构是一种特殊的数据结构的实现方式。在可持久化数据结构中，元素一旦建立不能修改和删除。每次修改操作，通过建立新的元素和重利用过去已经建立的元素实现。从而达到了保留数据结构的所有时刻版本的目的。,可持久化线段树简介,存储结构：指针实现。记录：左、右边界，左、右孩子，以及其他要维护的信息建树：调用建树过程，返回建好的树的根节点查询：直接查询对应历史版本的根结点，查询过程与普通线段树几乎一样,可持久化线段树简介,修改操作（核心）：修改操作返回一个新的根结点。对一个节点修改操作包括了递归修改和更新该节点信息两个过程。更新节点信息时，我们建立一个新的节点，新节点没有修改过的子节点设置为上一个历史版本的线段树中的节点，修改过的子节点设置为对应递归函数返回的节点标记：同样可以实现，与本文关系不大,可持久化线段树简介,在本题中的具体运用,以分析在一个点左下的点为例，我们可以按照y坐标的顺序建立一个维护x+y最大值的线段树。并以x坐标的顺序依次插入节点，这样我们就可以得到按照x坐标插入的线段树的各个历史版本，通过类似离线问题的处理方法，解决所有询问，时空复杂度均为nlog2n。是划分树的一种完美替代品。但对于点的修改会涉及到同时修改多个历史版本的线段树，情况复杂，这里不详细阐述。,总结,本文由一道简单的例题出发，着重分析了一类有关平面上点对的曼哈顿距离的问题。全文贯穿了去绝对值的思想。按照题目要求的不同分析了几类不同情况。这类问题的解决方法