算法合集之数据结构的联合.ppt

算法合集之数据结构的联合 第一页，共二十八页，2022年，8月28日 问题1 顽皮的猴子 问题描述： 有N（1<=N<=30000）只顽皮的猴子挂在树上。每只猴子都有两只手，编号为1的猴子的尾巴挂在树枝上，其他的猴子的尾巴都被别的猴子的某只手抓着。每一时刻，都有且只有一只猴子的某只手松开，从而可能会有一些猴子掉落至地面。输入一开始猴子们的情况和每一时刻松开手的情况，输出每只猴子落地的时间。 第二页，共二十八页，2022年，8月28日 问题1 顽皮的猴子 分析： 我们把猴子抽象成点，猴子的手抽象成边，题目就转化成一个连通图不断去边，求每个点离开编号为1的点所在的连通分量的时间。 2 3 5 4 1 1 2 3 3 第三页，共二十八页，2022年，8月28日 问题1 顽皮的猴子 分析： 把删边的顺序倒过来，问题转化为从一个无边的图不断添边，求每个点进入编号为1的点所在的连通分量的时间。我们自然的想到用并查集维护。 2 3 5 4 1 1 2 3 3 第四页，共二十八页，2022年，8月28日 问题1 顽皮的猴子 一个问题： 上面的算法中，当并查集中某个集合加入编号为1的点所在的集合时，需要把这个集合中的所有元素的时间记录一下。但是并查集并不支持“枚举集合元素”的功能，怎么办？ 3 5 Time[3]:=2 Time[5]:=2 1 ? 1 3 5 第五页，共二十八页，2022年，8月28日 问题1 顽皮的猴子 一个问题： 给每个并查集分配一个链表，记录这个集合中所有的元素。这样，能够方便的枚举集合中的元素。而在并查集合并的时候，链表也能够很快的合并。问题解决。 3 5 1 Nil 1 3 5 Nil 1 3 5 第六页，共二十八页，2022年，8月28日 数据结构的并联 问题1中，在并查集不支持枚举元素操作的时候，引入一个新的数据结构链表来辅助，是数据结构的一种联合方式：并联，这种联合成功的解决了问题。 定义： 我们将用多个数据结构共同对同一数据集合统计的方法叫做数据结构的并联。 第七页，共二十八页，2022年，8月28日 数据结构的并联 为了方便起见，先把一个数据结构支持的操作分为两类： 询问操作：顾名思义，就是获取该数据结构记录的某些信息的操作，而并没有改动数据结构里的元素及其相互关系。 维护操作：跟询问操作相反，改动数据结构中元素或元素的相互关系的操作，称为维护操作。 第八页，共二十八页，2022年，8月28日 数据结构的并联 并联的优点： 并联而成的新数据结构，支持组成它的数据结构的所有操作。 并联的缺点： 维护操作的时间复杂度存在瓶颈，是所有组成它的数据结构的维护操作复杂度的和。 第九页，共二十八页，2022年，8月28日 问题2 DynamicRankings 问题描述： 给定一个长度为N（1<=N<=50000）的正整数序列A（1<=A[i]<=MaxLongint），模拟以下操作： 1、改值操作C(i,j)：将A[i]的值改为j 2、询问操作Q(i,j,k)：程序输出A[i],A[i+1],…,A[j]这j-i+1个数中第k大的数。 第十页，共二十八页，2022年，8月28日 问题2 DynamicRankings 例如： N=6 A=[3,1,6,5,2,4] C(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] 输出：4 C(6,2) Q(3,6,1) [3,1,6,5,4,4] [3,1,6,5,4,4] [3,1,6,5,4,2] [3,1,6,5,4,2] 输出：6 [3,1,6,5,4,2] 第十一页，共二十八页，2022年，8月28日 问题2 DynamicRankings 分析： 单纯的算法必定会超时，我们需要设计一个对整数序列进行统计的高效数据结构，并且支持改值和查找指定区间中第k大的数。 问题过于复杂，先考虑简单一点的情况。 第十二页，共二十八页，2022年，8月28日 问题2 DynamicRankings 简化情况1： 每次询问Q(i,j)，要求程序输出A[i],A[i]+1,…,A[j]这j-i+1个数中最大的数。 解决方式： 只需用一颗线段树维护A序列，改值，询问操作都是O(LogN)的时间复杂度，完全满足题意。 第十三页，共二十八页，2022年，8月28日 问题2 DynamicRankings 简化情况2： 每次询问Q(k)，要求程序输出A[1],A[2],…,A[N]这N个数中，第k大的数。 解决方式： 用一颗平衡二叉树维护A序列即可，同样的，改值，