当前位置:首页 > 数据结构 > 左偏树 > 正文
洛谷P3377【模板】左偏树(可并堆)
3046+

题目大意:n个堆,现在需要对他们进行合并,并在合并的过程中,输出并删除某个堆的根结点。

题目描述

如题,一开始有N个小根堆,每个堆包含且仅包含一个数。接下来需要支持两种操作:

操作1: 1 x y 将第x个数和第y个数所在的小根堆合并(若第x或第y个数已经被删除或第x和第y个数在用一个堆内,则无视此操作)

操作2: 2 x 输出第x个数所在的堆最小数,并将其删除(若第x个数已经被删除,则输出-1并无视删除操作)

输入输出格式

输入格式:
第一行包含两个正整数N、M,分别表示一开始小根堆的个数和接下来操作的个数。

第二行包含N个正整数,其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。

接下来M行每行2个或3个正整数,表示一条操作,格式如下:

操作1 : 1 x y

操作2 : 2 x

输出格式:
输出包含若干行整数,分别依次对应每一个操作2所得的结果。

输入输出样例

输入样例#1:

5 5
1 5 4 2 3
1 1 5
1 2 5
2 2
1 4 2
2 2

输出样例#1:

1
2

说明

当堆里有多个最小值时,优先删除原序列的靠前的,否则会影响后续操作1导致WA。

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=1000,M<=1000

对于100%的数据:N<=100000,M<=100000

样例说明:

初始状态下,五个小根堆分别为:{1}、{5}、{4}、{2}、{3}。

第一次操作,将第1个数所在的小根堆与第5个数所在的小根堆合并,故变为四个小根堆:{1,3}、{5}、{4}、{2}。

第二次操作,将第2个数所在的小根堆与第5个数所在的小根堆合并,故变为三个小根堆:{1,3,5}、{4}、{2}。

第三次操作,将第2个数所在的小根堆的最小值输出并删除,故输出1,第一个数被删除,三个小根堆为:{3,5}、{4}、{2}。

第四次操作,将第4个数所在的小根堆与第2个数所在的小根堆合并,故变为两个小根堆:{2,3,5}、{4}。

第五次操作,将第2个数所在的小根堆的最小值输出并删除,故输出2,第四个数被删除,两个小根堆为:{3,5}、{4}。

故输出依次为1、2。

解题思路

左偏树,用于合并多个堆,每个结点需要记录左儿子lc、右儿子rc、值a和度c。父亲结点不比儿子小是大根堆;父亲结点不比儿子大是小根堆。如和合并两个小根堆呢?首先看他们的根结点,根结点值小的作为他们的根结点,因为最小是一定是根结点,然后另外一个堆和这个根结点原来的右儿子进行合并,合并后得到的子树根结点作为整棵树根结点的右儿子。这样递归执行下去,就可以把两个堆合并在一起,且满足堆的性质。但时间复杂度如何?要看堆的高度,高度越小越好。如何让他是log级别呢?这就需要记录每个结点的度——结点到有空子结点的结点的最短距离,如果自己有空子结点,那么度就为0,否则就是儿子最小的度+1。我们让左偏树左子树的度不比右子树小,这样就可以是log级别的高度!

为什么呢?如果一棵左偏树的度(根结点的度)是固定的,比如说度为k,那么这棵树(子树)的结点数至少是(2<<k)-1。度为0的子树结点数至少是1,如果左右儿子都是空子树就是1;度为1的子树结点数至少是3,因为右儿子度为0,至少1个,左儿子度不比右儿子小,也至少1个;如果度为2,那么右儿子度为1,至少3个,左儿子也是如此……也就是说,当左儿子的度根右儿子的度一样的时候,度为k的结点数量最少,而且是一颗完全二叉树、满二叉树。因此,一个结点数为n的左偏树,度再大也是log级别的。每次合并,不断与右儿子合并,因为右儿子度小,深度小!

合并两个堆x和y,如果其中一个是空的,那么非空的根还是根,其他不变就行;如果x小,就合并x的右儿子和y,否则交换x和y的位置后,还是合并x的右儿子和y;合并完后,如果发现右儿子的度更大,那么交换他的左右子树,保持左偏树的性质,控制复杂度;树的结构确定后,根据右儿子的度确定父亲结点的度;最后返回合并后的根结点。

用并查集记录第i个数所在的堆,合并两个堆的时候,用左偏树进行合并——取最小的作为根结点,然后合并另外一个堆和根的右儿子,因为右儿子度小些;删除根结点,即合并根的左右儿子。需要注意的是,合并之后返回新的根结点k,然后两个堆的所有节点的祖先都是新的根结点,对于删除根的操作,f[lc] = f[rc] = k是不够的,因为他们的子孙可能有些节点直接指向原来的根r,因此需要加上f[r] = k;当然仅写一句也是不够的,因为k可能是lc(或者rc),那么就会导致f[r] = lc,f[lc] = r的情况,形成环则并查集查找时会死循环,因此需要加上f[k] = k,即新根和旧根的祖先都是新根。

程序实现

About

坚决不Copy代码!

本文标签:,,,

洛谷P3377【模板】左偏树(可并堆):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!