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

一类平面点对曼哈顿距离问题的探究常州市第一中学陈子旸一类平面点对曼哈顿距离问题的探究常州市第一中学陈子旸曼哈顿距离问题在信息学竞赛题目中十分常见曼哈顿距离的定义：在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和讨论将围绕一类平面上最大、最小曼哈顿距离点对问题展开曼哈顿距离问题在信息学竞赛题目中十分常见目录引例情况一：离线查询、无修改情况二：在线查询、修改情况三：在线查询、无修改其他方法的讨论总结目录引例引例(magic)题目大意：在一个ｋ(k<=7)维的空间中，有ｎ(n<=100000)个点，要求求出在这些点对中曼哈顿距离最远的点对之间的曼哈顿距离。引例(magic)题目大意：在一个ｋ(k<=7)维的空间中，例题分析直接暴力枚举点对？显然TLE！两点间曼哈顿距离的计算公式：以平面为例dist=|x1-x2|+|y1-y2|绝对值处理太麻烦！dist=|(x1-y1)-(x2-y2)|,(x1>x2&&y1>y2)||(x1<x2&&y1<y2)|(x1+y1)-(x2+y2)|,(x1>x2&&y1<y2)||(x1<x2&&y1>y2)例题分析直接暴力枚举点对？显然TLE！两点间曼哈顿距离的计算例题分析怎么处理？分类讨论？？？？ＮＯ！！！完全不需要！|x|+|y|>=|x+y|也就是说：如果我们计算时如果不满足条件，所计算出的值会比真实值小，不会更新答案！例题分析怎么处理？分类讨论？？？？ＮＯ！！！完全不需要！|x例题分析

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