[BZOJ2333/Luogu3273][SCOI2011]棘手的操作(可并堆,左偏树)

发布于 2018-02-23  244 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2333/Luogu3273][SCOI2011]棘手的操作(可并堆,左偏树)

Description

有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:
U x y: 加一条边,连接第x个节点和第y个节点
A1 x v: 将第x个节点的权值增加v
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v
A3 v: 将所有节点的权值都增加v
F1 x: 输出第x个节点当前的权值
F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值
F3: 输出所有节点中,权值最大的节点的权值

Http

BZOJ
Luogu

Tag

可并堆,左偏树

解决思路

考虑到题目中所有的询问操作都是求最大值,再看到第一种操作只有合并没有分离,那么可以想到用可并堆来维护每一个联通块,至于整个连通块的修改可以用\(lazy\)标记来维护。下面依次具体来看每一个操作。
U x y: 加一条边,连接第x个节点和第y个节点,这个直接分别找到\(x\)和\(y\)所在的可并堆的根,若不在同一个可并堆则合并两个可并堆。注意,这里跳祖先不能用并查集,具体原因下面会说。时间复杂度\(O(logn)\)
A1 x v: 将第x个节点的权值增加v,在可并堆中分离出节点\(x\),然后把\(x\)的权值修改了后再与\(x\)原来所在的可并堆合并。注意,由于有\(lazy\)标记,在分离之前要把从根到\(x\)路径上的所有\(lazy\)都下放。具体分离的步骤是先把\(x\)的两个儿子合并,然后把儿子合并后的新根连上原来\(x\)的父亲,同时修改父亲对应的儿子指针。时间复杂度\(O(logn)\)
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v,跳到\(x\)所在可并堆的根,对根打上\(lazy\)标记。时间复杂度\(O(logn)\)
A3 v: 将所有节点的权值都增加v,在全局维护一个\(allsum\)表示所有\(A3\)操作之和,每一次要输出的时候再加上即可。时间复杂度\(O(1)\)
F1 x: 输出第x个节点当前的权值,类似的,要先从根向下下放所有的\(lazy\)标记再得到值。时间复杂度\(O(logn)\)
F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值,跳到根后输出根的值。时间复杂度\(O(logn)\)
F3: 输出所有节点中,权值最大的节点的权值,由于权值最大的值一定是可并堆的根,所以可以在全局再维护一个代删除的堆,每一次有对可并堆的堆顶的修改时就在这个全局的堆中进行修改,那么\(F3\)操作就直接输出这个堆顶即可。为了方便,可以用两个系统堆来实现带删除的堆的操作,具体来说,用一个堆表示实际的堆,另一个标记垃圾堆,每一次要删除实际堆中的元素时,把这个元素丢入垃圾堆中,当实际堆与垃圾堆的堆顶相同时,同时弹出两个堆的堆顶。时间复杂度\(O(logn)\)
至于为什么不能用路径压缩并查集来维护堆顶。由于这里再可并堆上有\(lazy\)标记用来下放,那么至少需要带权并查集来维护,又因为\(lazy\)是在不断下放的,那么可能并查集还没有更新到,\(lazy\)就已经下放了。再加上有分离出某一个点修改再丢回去的操作,这时候带权并查集的权就会更加混乱。所以不能路径压缩。
这里用左偏树实现可并堆。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2333/Luogu3273][SCOI2011]棘手的操作(可并堆,左偏树)


HNCJ OIer