AC. 梦想

frank_c1

[BZOJ 3674] 可持久化并查集

发布于2015年12月16日 | 暂无评论 | 834阅读 | 可持久化,数据结构

题目描述

有n个集合,m个操作。(0<n,m<=2*10^5)操作有下列3种形式。

1 a b 合并a,b所在集合;

2 k 回到第k次操作之后的状态(查询算作操作);

3 a b 询问a,b是否属于同一集合,是则输出1否则输出0。

本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0。

注:3674是3673的加强版,在此不给出3673的题面。

题目解析

首先,我们考虑并查集是用数组实现的。所以如果有可持久化数组就可以实现可持久化并查集。

可持久化数组怎么实现呢?我们用线段树来做,每次更新时不修改原值,而是一路新建结点。然后我们保存每个版本的树根。假设每次操作O(1),由于每次新建结点个数为O(logn),所以纯可持久化数组的时间和空间复杂度均为O(mlogn)。

下面来考虑并查集。3673由于数据特弱,不加任何优化甚至乱搞均可水过。3674必须要加优化,有两种方案,按秩合并或路径压缩。黄学长打的是按秩合并,空间比较省,时间复杂度也较优。然而本蒟蒻并不会按秩合并,只能指望路径压缩。会发现路径压缩每次修改不止一个节点的值,怎么办?还是一样的办法,在可持久化数组上改,改完了保存本次操作最后一次修改的版本。这样的话时间和空间复杂度貌似不止O(mlogn),不过还是可以过的。