算法合集之回到起点一种突破性思维.docVIP

回到起点——一种突破性思维 南京市外国语学校 朱泽园 [关键字] 起点 类比 分离集合森林 [摘要] 高层次的信息学竞赛已经不是单纯一个算法、一种数据结构间的较量，而是对思维方法、创新能力的考验。本文旨在深刻剖析一种突破性思维——回到起点，亦即敢于放弃当前成果，回到初步分析处展开理性思考的可贵品质。 本文第一章提出一个已被经典算法解决的普通题。第二章对这道题展开讨论，简述了经典的解决方案，而后模拟本文主线描绘的思维方式进行思考，提出一个被遗忘的简单算法，并进行优化和类比，精确计算复杂度后问题被完美解决。 第三章对本思维方式在两个例题中的应用作了对比和升华，辩证地以前进性和曲折性的统一阐述了这类思想的重要性。 [目录] §1 问题的提出 §1.1 问题描述 §1.2 问题的初步分析——离散化 §1.3 一个朴素的想法 §2 问题的解决 §2.1 经典算法 §2.2 另类算法 §2.3 通过完整的路径压缩完善算法 §2.4 秩的建立 §2.5 小结 §3 总结 [正文] §1 问题的提出 §1.1 问题描述 [USACO 2.1 Shaping Regions改编] N个不同颜色的不透明长方形（1≤N≤3000）被放置在一张长宽分别为A、B的白纸上。这些长方形被放置时，保证了它们的边与白纸的边缘平行。所有的长方形都放置在白纸内，所以我们会看到不同形状的各种颜色。坐标系统的原点（0,0），设在这张白纸的左下角，而坐标轴则平行于纸边缘。 输入： 第1行：A ， B 和 N, 由空格分开。 第2~N+1行：按照从下往上的顺序，每行输入的是一个长方形的放置。为五个数　llx, lly, urx, ury, color　这是长方形的左下角坐标，右上角坐标和颜色。其中color为整数。0=llx,urx=A，0=lly,ury=B。所有坐标（包括A、B）都是0至10^9的实数。 颜色 1和底部白纸的颜色相同。 输出： 输出文件应该包含一个所有能被看到颜色连同该颜色的面积（保留小数点后三位）的列表（即使颜色的编号不是连续的）。按color的增序顺序输出，不要输出面积为0的颜色。 样例输入： 20 20 32 2 18 18 20 8 19 19 38 0 10 19 4 样例输出 1 91.0002 84.0003 187.0004 38.000 §1.2 问题的初步分析——离散化 自IOI1998的Picture问题始，和平面放置矩形有关的问题已在信息学竞赛中屡见不鲜，其最基本的预处理操作是将平面离散化。如图1 将平面理解成网格，也就是说将所有在矩形坐标中出现过的x坐标（y坐标）提出，排序后删除重复，并按顺序编号。任意两个相邻格点连成的线段，称之为“元线段”；两个相邻离散过的x坐标（y坐标）之间的区域，称之为“离散列”（“离散行”）；任意一个离散行和离散列的公共部分称之为“离散格”。对每个矩形坐标相应地存在一个格点坐标与之对应。 这有助于处理坐标为实数，或者范围超过longint的问题。离散化之后，任意矩形顶点坐标均可表示为1到2N之间的整数：利用hash策略可以将实数坐标在O(1)时间内转化为对应的整点坐标，更显然地，直接读表可以在O(1)时间内将格点坐标转化为原矩形坐标。因此后文只考虑坐标为整数，且范围在1到2N之间的N个格点矩形的问题。 §1.3 一个朴素的想法 最朴素算法的实现取自于简单的灌水（Floodfill）算法。就是用2Nx2N的数组，分别记录每个离散格的颜色，初始时全部无色。自顶至下处理每一个矩形，将其覆盖之下无色的部分全部填上颜色。 考虑到空间可能无法承受，改进的措施是每次处理一个离散行（2N的一维数组），自顶向下处理每个矩形，如果这个矩形与当前离散行有公共部分，那么就和前面类似地，将无色部分涂色，如图2： 该方法基本不会增加程序运行时间，只是时间复杂度系数稍微增加了些，并不影响大局。 §2 问题的解决 §2.1 经典算法 解决这类问题的经典算法莫过于线段树。同样是对每个离散行做处理，该算法利用了O(N)空间的树型数据结构。如图3，构建一个线段树： 该数据结构主要支持的操作是，给定线段[l,r]和属性X组成的操作对(l,r,X)，意思是将区间[l,r]赋予属性X。称“在P节点上进行(l,r,X)操作”为P(l,r,X)，具体操作如下： 例如图3中红色的部分是处理Root(3,8,X)操作后被赋予X属性的结点。可以证明对每个操作Root(l,r,X)，其时间复杂度为O(logN)（N是叶结点个数，也就是区间范围）。 观察本题需要这个数据结构支持怎样的特殊操作： 插入一条颜色为X的线段[l,r]，该区间[l,r]上原有颜色不被替换，其余部分染上颜色X。 返回所有颜色当前的覆盖量。（该操作只将在该离散行