《国家集训队2005论文集 黄刚》由会员分享，可在线阅读，更多相关《国家集训队2005论文集 黄刚（28页珍藏版）》请在金锄头文库上搜索。
1、数据结构的联合长沙市雅礼中学 黄刚问题1 顽皮的猴子问题描述：有N（1=N=30000）只顽皮的猴子挂在树 上。每只猴子都有两只手，编号为1的猴子的 尾巴挂在树枝上，其他的猴子的尾巴都被别 的猴子的某只手抓着。每一时刻，都有且只 有一只猴子的某只手松开，从而可能会有一 些猴子掉落至地面。输入一开始猴子们的情 况和每一时刻松开手的情况，输出每只猴子 落地的时间。 问题1 顽皮的猴子分析： 我们把猴子抽象成点，猴子的手抽象成边， 题目就转化成一个连通图不断去边，求每个 点离开编号为1的点所在的连通分量的时间。235411233问题1 顽皮的猴子分析： 把删边的顺序倒过来，问题转化为从一个无 边的图
2、不断添边，求每个点进入编号为1的点 所在的连通分量的时间。我们自然的想到用 并查集维护。235411233问题1 顽皮的猴子一个问题： 上面的算法中，当并查集中某个集合加入编 号为1的点所在的集合时，需要把这个集合中 的所有元素的时间记录一下。但是并查集并 不支持“枚举集合元素”的功能，怎么办？3 5Time3:=2 Time5:=21?1 3 5问题1 顽皮的猴子一个问题： 给每个并查集分配一个链表，记录这个集合 中所有的元素。这样，能够方便的枚举集合 中的元素。而在并查集合并的时候，链表也 能够很快的合并。问题解决。3 51Nil135Nil1 3 5数据结构的并联问题1中，在并查集不支持
3、枚举元素操作的时 候，引入一个新的数据结构链表来辅助，是 数据结构的一种联合方式：并联，这种联合 成功的解决了问题。定义： 我们将用多个数据结构共同对同一数据集合 统计的方法叫做数据结构的并联。数据结构的并联为了方便起见，先把一个数据结构支持的操 作分为两类：询问操作：顾名思义，就是获取该数据结构 记录的某些信息的操作，而并没有改动数据 结构里的元素及其相互关系。维护操作：跟询问操作相反，改动数据结构 中元素或元素的相互关系的操作，称为维护 操作。数据结构的并联并联的优点： 并联而成的新数据结构，支持组成它的数据 结构的所有操作。并联的缺点： 维护操作的时间复杂度存在瓶颈，是所有组 成它的数据
4、结构的维护操作复杂度的和。问题2 DynamicRankings问题描述： 给定一个长度为N（1=N=50000）的正整 数序列A（1=Ai=MaxLongint），模拟以 下操作： 1、改值操作C(i,j)：将Ai的值改为j 2、询问操作Q(i,j,k)：程序输出 Ai,Ai+1,Aj这j-i+1个数中第k大的数。 问题2 DynamicRankings例如： N=6 A=3,1,6,5,2,4C(5,4)3,1,6,5,2,4 3,1,6,5,2,4 3,1,6,5,4,4 Q(2,5,3)3,1,6,5,4,4 3,1,6,5,4,4 输出：4C(6,2)Q(3,6,1)3,1,6,5,
5、4,4 3,1,6,5,4,4 3,1,6,5,4,2 3,1,6,5,4,2 输出：63,1,6,5,4,2 问题2 DynamicRankings分析：单纯的算法必定会超时，我们需要设计一个 对整数序列进行统计的高效数据结构，并且 支持改值和查找指定区间中第k大的数。 问题过于复杂，先考虑简单一点的情况。问题2 DynamicRankings简化情况1： 每次询问Q(i,j)，要求程序输出 Ai,Ai+1,Aj这j-i+1个数中最大的数。解决方式： 只需用一颗线段树维护A序列，改值，询问操 作都是O(LogN)的时间复杂度，完全满足题 意。问题2 DynamicRankings简化情况2：
6、 每次询问Q(k)，要求程序输出 A1,A2,AN这N个数中，第k大的数。解决方式： 用一颗平衡二叉树维护A序列即可，同样的， 改值，询问操作也只需要O(LogN)的时间。问题2 DynamicRankings问题的嵌套：现在，两个很简单的问题“嵌套”在了一起，成 了一个棘手的问题，使得原先的方法都失效 了。既然问题能够“嵌套”，那我们原先解决问题的 数据结构是不是也能够“嵌套”呢？问题2 DynamicRankings数据结构的嵌套： 考虑一颗这样的线段树：它维护整个A序列， 而它的每个节点V，设表示的区间为i,j，拥 有一颗平衡二叉树，维护Ai,Ai+1,Aj。为下文方便起见，暂时称之为“
7、嵌套树”。问题2 DynamicRankingsN=4的一颗嵌套树： 容易证明空间复杂度 是O(NLogN)。1,4A3A4A2A13,4A3A41,2A2A11,1A1 2,2A2 3,3A3 4,4A4问题2 DynamicRankings改值操作C(i,j)： 在线段树中将包含Ai的节点找出来，再在相 应的平衡树中更新。 例如N=4， A=1,4,2,3 改值C(3,1)时间复杂度O(Log2N)。1,43 42 13,42 3 1,24 11,11 2,24 3,32 4,431,43 42 13,42 33,323,41 23,311,41 21 4问题2 DynamicRankin
8、gs询问操作Q(i,j,k)：如果按照线段树求区间最大值的方法：将 i,j分解为若干个嵌套树中的区间并，分别 求出每个子区间中第k大的数，再合并，这 样是行不通的！我们无法根据几个区间的第k大的数求出这 些区间并的第k大的数。问题2 DynamicRankings另辟蹊径： 将问题逆转过来，设询问Q(i,j,w) ，表示求正 整数w在Ai,Ai+1,Aj中排第几，应该怎 么做？将i,j区间在嵌套树中分解为若干子区间的并 ，分别求出每个区间中，有多少个比w大的 数，最后把结果合并，就能够求出w在 Ai,Ai+1,Aj的排位。问题2 DynamicRankings另辟蹊径： 例如，N=4，A=1,
9、4,2,1，询问Q(2,4,2)， 即求2在A2,A3,A4中的排位。1,24 11,11 2,24 3,323,41 24,411,41 21 42,243,41 21个数比2大0个数比2大2的排位是1+0+1=2时间复杂度O(Log2N)问题2 DynamicRankings另辟蹊径：w越大，它的排位肯定越靠前。我们不妨二分枚举w，使得w在 Ai,Ai+1,Aj中排位为k，再求出 Ai,Ai+1,Aj中不大于w的最大的数，设 为T(i,j,w)。则Q(i,j,k)的答案就是T(i,j,w)。问题2 DynamicRankingsT(i,j,w)的求法： 此时，我们可以用线段树求区间最大值的
10、类 似方法求出T(i,j,w)。 将i,j区间在嵌套树中分解为若干子区间的并 。对每个子区间，找出不大于w的最大的数 ，若找不到，记答案为。所有的子区间的 答案中的最大值，就是T(i,j,w)。问题2 DynamicRankingsT(i,j,w)的求法： 例如，N=4，A=1,4,2,1，求T(2,4,3)1,11 2,24 3,323,41 24,411,41 21 41,24 12,243,41 22T(2,4,3)=Max(2,)=2时间复杂度O(Log2N)问题2 DynamicRankings回顾一下整个算法：使用嵌套树作为数据结构，空间复杂度是 O(NLogN)。改值操作的时间复
11、杂度O(Log2N)。询问操作Q(i,j,k)，先二分枚举求出w，再求出 T(i,j,w)，时间复杂度是 O(LogMaxLongint*Log2N)整个问题的复杂度是 O(MLogMaxLongintLog2N)。数据结构的嵌套总结：上例中成功的运用了数据结构的嵌套解决了 问题。数据结构的嵌套，无疑是一种本质的变化， 形成新的更强力的数据结构，但也有明显的 缺点：空间复杂度大幅增高。能不能真正发挥出数据结构嵌套的威力，无 疑还是要靠我们的运用方式了。总结数据结构数据结构数据结构。数据结构的联合，肯定不止上面提到的两种 方式。敏捷的思维，灵活的运用，才能将数据结构 的联合应用于信息学竞赛当中。
