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

一类平面点对曼哈顿距离问题的探究常州市第一中学陈子旸曼哈顿距离问题在信息学竞赛题目中十分常见曼哈顿距离的定义：在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和讨论将围绕一类平面上最大、最小曼哈顿距离点对问题展开目录引例情况一：离线查询、无修改情况二：在线查询、修改情况三：在线查询、无修改其他方法的讨论总结引例(magic)题目大意：在一个ｋ(k=7)维的空间中，有ｎ(n=100000)个点，要求求出在这些点对中曼哈顿距离最远的点对之间的曼哈顿距离。例题分析直接暴力枚举点对？显然TLE！两点间曼哈顿距离的计算公式：以平面为例dist=|x1-x2|+|y1-y2|绝对值处理太麻烦！dist=|(x1-y1)-(x2-y2)|,(x1x2&&y1y2)||(x1x2&&y1y2)|(x1+y1)-(x2+y2)|,(x1x2&&y1y2)||(x1x2&&y1y2)例题分析怎么处理？分类讨论？？？？ＮＯ！！！完全不需要！|x|+|y|=|x+y|也就是说：如果我们计算时如果不满足条件，所计算出的值会比真实值小，不会更新答案！例题分析处理时，只需要分别统计|(x1+y1)-(x2+y2)|的最大值和|(x1-y1)-(x2-y2)|的最大值，最后再取大的作答案就行了。高维推广处理方法类似，以三维为例，只要统计x+y+z,x+y-z,x-y+z,x-y-z四类情况的答案就可以了。•通过引例，我们初步了解了这类问题的特点，同时发现了解决这类问题的一个重要的思想：去绝对值•在引例中，运用了求最大值的条件和一个绝对值不等式，避免了分类讨论。但实际运用时往往要求最小值，我们不得不分类讨论解决这类问题，接下来的部分按题目的不同要求分析了几类不同情况。情况一：离线查询，无修改•例题2(DONUT)•题目大意：在一个平面上有两类点Ａ，Ｂ。对于每个Ｂ类点求出离他曼哈顿距离最近的A类点与它的曼哈顿距离，其中Ａ类和Ｂ类点的个数都不超过50000个，点的坐标范围在长整数范围内。例题2分析dist=|(x1+y1)-(x2+y2)|,(x1x2&&y1y2)||(x1x2&&y1y2)|(x1-y1)-(x2-y2)|,(x1x2&&y1y2)||(x1x2&&y1y2)以分析在一个点左下的点为例例题2分析•把所有点按照x的值排序，依次插入处理•处理一个点时，所有插入的点的x的值都小于当前点，所以只需要满足y的条件就可以了•处理对y的限制，只需要维护一棵维护x+y最大值的线段树，能够支持单点插入和区间查询最值两个操作就可以了情况二：在线查询、带修改•例题3(DONUTEXT)•在一个平面上给定一个点集，可以动态地插入或删除点集中的点，并询问离点集中某个点最近的点到该点的曼哈顿距离。点集的大小不超过100000。例题3分析在线，带修改。离线算法神马的不管用了……我们需要一个能同时处理两个维度有序性的数据结构有没有想到区间第k大数问题？例题3分析•在区间第k大数问题中，需要同时维护数在原序列中的位置和数的大小两个序关系•在区间第k大数问题中，可以使用归并树这一结构•下面来看一下如何把归并树运用到本题中例题3分析123456781347256813472568134752681347256于是我们在O(nlog22n)的时间复杂度和O(nlog2n)的空间复杂度内解决了这个问题情况三：在线查询，无修改•例题4(DONUTEXT2)•题目大意：在一个平面上给定一个点集，查询距离点（x，y）最近的点离它的曼哈顿距离，这里的x，y由上两问的答案经过某种变化得到。例题4分析从题面分析，这题似乎比上一题目要简单，因为没有修改操作若果直接套用上一题的做法，那这题就没有存在的意义了所以一定有效率更高的算法！如何超越nlog22n?我们想到了求解区间第k大数的又一神器划分树例题4分析直观地理解划分树，就是把快排的过程建成一棵树13475268134275681234567812345678注意：划分树中每个数要维护：该节点中，在这个数之前被分到左子区间的数的个数，例如对于根结点中的7，这个值就是3例题4分析•划分树有很好的性质：•根结点记录原序列•下一层中被划分成的两个区间中的数字的相对顺序与上一层相同•从一个节点划分出的左子节点中的元素小于右子节点中的元素这些性质可以帮助我们解决例题4例题4分析13475268134275681234567812345678134751347557其他方法的讨论当然，在处理这类问题的时候还有其他方法四分树可持久化数据结构（线段树）树套树四分树在这类题中的运用回归问题本质：二维RMQ查询一维线段树的拓展：四分树一个矛盾：四分树在这类题中的运用巨大的空间开销如何解决？只把有用的节点建立起来！总结•本文由一道简单的例题出发，着重分析了一类有关平面上点对的曼哈顿距离的问题。全文贯穿了去绝对值的思想。按照题目要求的不同分析了几类不同情况。这类问题的解决方法灵活多变，与题目中限制条件的相关性很大，与其他问题也有不同程度的联系。对于这样一类问题的分析与思考，锻炼了我们根据具体情况设计算法和数据结构的能力。