CTSC’2005国家集训队论文 南京市外国语学校 朱泽园
3、父节点为自身的节点定义为根节点。
注意：对于p[i]!=i的节点，也就是分离集合森林中的非根节点，其next[i]已经失去意义。而对于根节点，必然有next[i] = i+1。这一点将为2.4节服务。
与图5相同，这里仍对上文数据给出图示及文字解释（因为next/color的定义与§2.2类似，因此对其改变我们不多赘述，将重点放在分离集合森林的构建）：
i p next[i] color[i] 1 颜色1 覆盖[2,6)
i p next[i] color[i] 1 2 颜色2 覆盖[4,7)
i p next[i] color[i] 1 5 2 颜色3 覆盖[1,9)
i p next[i] color[i]
7 6 4 图6
1 8 9 3 2 8 9 1 3 3 5 6 1 4 6 7 1 8 5 3 2 1 5 8 9 1 6 8 9 2 7 8 9 3 8 8 9 3 6 4 7 8 1 1 2 NIL 2 5 6 1 5 3 3 5 6 1 4 4 6 7 1 5 6 7 1 6 6 7 2 7 7 8 NIL 8 8 9 NIL 6 7 8 2 1 1 2 NIL 3 2 5 6 1 4 3 5 6 1 5 4 5 6 1 6 5 5 6 1 6 6 7 NIL 7 7 7 8 NIL 8 8 8 9 NIL 1 1 2 NIL 2 2 3 NIL 3 3 4 NIL 4 4 5 NIL 5 5 6 NIL 6 6 7 NIL 7 7 8 NIL 8 8 9 NIL
第一次用颜色1的线段覆盖[2,6），因为所有节点自成集合，故本次覆盖操作
第 9 页 共 11 页
CTSC’2005国家集训队论文 南京市外国语学校 朱泽园
将2..5节点合并，5为他们的根节点（代表元），显然next[2..4]失去其意义（在表格中用X表示）。
第二次用颜色2的线段覆盖[4,7)，i指针来到l=4，根据分离集合森林的定义，需要找到其所在集合的根节点（该集合的代表元），也就是节点p[4]=5。紧接跳转下一个集合，也就是节点6。指针i移动到6，并且修改color[6]。最后压缩路径——前面所经过的所有点x的p[x]都指向6——5和6所在的集合合并，6成为新的根节点。
第三次用颜色3的线段覆盖[1,9)，i指针先来到1，修改color[1]后跨入next[1]=2所在的集合，发现其已染色，通过i?p[p[2]]=6以及i?next[i]=7跨越该集合，并对7、8两个独立的集合染色。最后1、2、7、8所在集合进行总合并。8为新的集合的根节点（代表元）。
§2.4 秩的建立
所谓秩，就是一个集合(树)所含的节点个数。对分离集合的合并，采取将节点数多的集合(树)，附着在节点数少的集合(树)上的策略，可以将集合的合并复杂度降至平摊的O(1)。这一个过程需要在上文蓝色粗斜体部分，即确定合并后新根节点的部分稍加修改，选取秩最大的树根作为新的根节点（代表元）即可。注意到这时对根节点不一定有next[i] = i+1。
一共有最多2N个集合，合并次数不超过2N-1，对当前离散行的处理时间复杂度仅为O(N)，整个算法的时间复杂度为O(N2)。
§2.5 小结
摒弃当今主流的线段树算法，回到起点，对朴素算法进行改进的思想实属不易。但其后算法的完全建立，思维过程极其缜密：首先找到冗余进行修改，旨在量变——某种意义上提高算法对部分数据的运行效率；发现算法的优越之处后，展开类比，将类似数据结构、算法的自身优点吸取，并进行改进；最后大步伐迈向让算法复杂度质变的目标。
§3 总结
希腊传说弗里吉亚国国王打了一个戈尔迪之结，预言称能解开它的人将统治
整个亚洲。亚历山大大帝认为它在预言中找到了自己的命运归宿，拿起长剑，径直将结劈开。有人说亚历山大将绳劈开是“作弊”的行为，但或许奥林匹斯山诸神寻找的就是如此少说多做的决断力？
面对多元化的世界，我们总会有这种“答案意识过强”的状态，就是这种倾向：对答案进行快速的设想，迅速沿那条道兴高采烈地出发，却并没在意先前设想的正确性、全面性。被自己创造的无形障碍蒙蔽实乃可惜，因此我们不能因片面的认识，或对放弃眼前利益的恐惧而裹足不前，偶尔我们也需要此类果敢与魄力。这正是前进性和曲折性的统一。
问题的表示往往比答案更重要，答案不过乃数学或实验。要提出新的问题、新的可能性、从某个新的角度考虑一个旧问题，都要求创造性的想象力，回到起点对问题重新定义，这才是真正的科学进步之所在。
第 10 页 共 11 页
CTSC’2005国家集训队论文 南京市外国语学校 朱泽园
[参考资料]
i. 《Introduction to Algorithms》
by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ii. 《The Art of Computer Programming》
by Donald E. Knuth
iii. 《The Computer Science and Engineering Handbook》
by Allen B. Tucker, etc.
iv. 《实用算法的分析和程序设计》
by 吴文虎 王建德
v. http://get-me.to/oi 辛韬同学提供的BalticOI2004解答
[感谢]
1、感谢辽宁省的辛韬同学对我的大力帮助（包括部分算法和证明）。
2、感谢江苏省青少年信息学（计算机）奥赛委员会教练组全体老师对我的指导。
3、感谢我的母校江苏省南京市外国语学校的老师给我的支持。 4、感谢我的家人给我的关怀。 5、感谢所有的信息学好友！
第 11 页 共 11 页
