可持久化并查集

题目描述

有 $n$ 个集合，$m$ 个操作，操作分为三种：

1. 1 a b —— 合并 $a,b$ 所在集合
2. 2 k —— 回到输入的第 $k$ 次操作之后的状态
3. 3 a b —— 询问 $a,b$ 是否属于同一集合，是则输出 $1$ 否则输出 $0$

强制在线

每个操作强制在线，需要对输入的 $a,b,k$ 进行运算得到真实的 $a,b,k$ 后再执行操作，运算方法为：

$$x = x \oplus \text{lastans}$$

其中 $\text{lastans}$ 表示上一个询问的答案，其初始值为 $0$。

输入格式

第一行为 $n, m$。

接下来 $m$ 行描述了每个操作，按照题目描述中所述的格式。

输出格式

对于每个询问操作，输出一个结果，每个结果占一行。

数据范围

$0 < n, m \le 2 \times 10^5$

输入样例

5 6
1 1 2
3 1 2
2 1
3 0 3
2 1
3 1 2

输出样例

1
0
1

样例解释

初始状态

• 有5个元素：1,2,3,4,5，初始时每个元素单独一个集合
• $\text{lastans} = 0$

操作1：1 1 2

• 原输入：1 1 2
• 不需要解密（不是a,b,k运算）
• 执行：合并元素1和2的集合
• 状态：集合 {1,2}, {3}, {4}, {5}

操作2：3 1 2

• 原输入：3 1 2
• 解密：$a = 1 \oplus \text{lastans} = 1 \oplus 0 = 1$, $b = 2 \oplus 0 = 2$
• 执行：查询1和2是否在同一集合
• 结果：是，输出 1
• $\text{lastans} = 1$

操作3：2 1

• 原输入：2 1
• 解密：$k = 1 \oplus \text{lastans} = 1 \oplus 1 = 0$
• 但k应该是操作编号，从1开始，0无效。实际上题目中说的是"回到输入的第k次操作之后的状态"，k应该是操作序号
• 这里k=0，应该回到初始状态（第0次操作后）
• 执行：回退到初始状态（所有元素单独成集合）
• 状态：集合 {1}, {2}, {3}, {4}, {5}

操作4：3 0 3

• 原输入：3 0 3
• 解密：$a = 0 \oplus \text{lastans} = 0 \oplus 1 = 1$, $b = 3 \oplus 1 = 2$
• 执行：查询1和2是否在同一集合
• 结果：否（刚刚回退到初始状态），输出 0
• $\text{lastans} = 0$

操作5：2 1

• 原输入：2 1
• 解密：$k = 1 \oplus \text{lastans} = 1 \oplus 0 = 1$
• 执行：回到第1次操作之后的状态（即操作1执行后的状态）
• 状态：集合 {1,2}, {3}, {4}, {5}

操作6：3 1 2

• 原输入：3 1 2
• 解密：$a = 1 \oplus \text{lastans} = 1 \oplus 0 = 1$, $b = 2 \oplus 0 = 2$
• 执行：查询1和2是否在同一集合
• 结果：是（回到了操作1之后的状态），输出 1
• $\text{lastans} = 1$

输出：

1
0
1

问题分析

这是一个可持久化并查集问题，需要支持：

1. 合并操作：合并两个集合
2. 查询操作：查询两个元素是否在同一集合
3. 版本回溯：回到之前某个操作之后的状态

关键挑战

• 并查集的路径压缩会改变数据结构，使得回退困难
• 需要记录每个操作后的完整状态

解决方案：可持久化数组 + 按秩合并

思路：

1. 不使用路径压缩，使用按秩合并（union by rank/size）
2. 用可持久化数组维护每个元素的父节点和集合大小/深度
3. 每个操作创建一个新版本

数据结构设计

可持久化数组

使用可持久化线段树或可持久化数组维护：

• fa[i]：元素i的父节点
• dep[i] 或 size[i]：集合的深度或大小（用于按秩合并）

操作实现

• 合并操作：

  1. 找到a和b的根节点（可能需要多次查找，没有路径压缩）
  2. 如果根不同，比较两个集合的大小/深度
  3. 将较小的集合合并到较大的集合中
  4. 更新父节点和深度/大小信息

• 查询操作：

  1. 找到a和b的根节点
  2. 比较根节点是否相同

• 版本回溯： 直接切换到对应的版本

时间复杂度

• 查找操作：$O(\log n)$（没有路径压缩，树的高度由按秩合并控制在 $O(\log n)$）
• 合并操作：$O(\log n)$
• 创建新版本：$O(\log n)$
• 总复杂度：$O(m \log n)$

算法步骤

版本管理

每个操作创建一个新版本，版本号就是操作序号。

查找操作（没有路径压缩）

def find(version, x):
    while fa[version][x] != x:
        x = fa[version][x]
    return x

合并操作

def union(version, a, b):
    ra = find(version, a)
    rb = find(version, b)
    if ra == rb:
        return version  # 已经在同一集合
    
    # 按秩合并：将深度小的合并到深度大的
    if dep[version][ra] < dep[version][rb]:
        ra, rb = rb, ra
    
    # 创建新版本
    new_version = copy_version(version)
    
    # 合并：将rb的父节点设为ra
    fa[new_version][rb] = ra
    
    # 如果深度相同，深度加1
    if dep[version][ra] == dep[version][rb]:
        dep[new_version][ra] += 1
    
    return new_version

查询操作

def query(version, a, b):
    return 1 if find(version, a) == find(version, b) else 0

版本回溯

def back_to_version(k):
    # 直接使用版本k的状态
    return k

强制在线处理

对于每个操作：

1. 读取操作类型和参数
2. 如果是类型2或3，需要对参数进行解密：
   • $a = a \oplus \text{lastans}$
   • $b = b \oplus \text{lastans}$
   • $k = k \oplus \text{lastans}$
3. 执行操作，更新当前版本
4. 如果是查询操作，输出答案并更新 $\text{lastans}$

可持久化实现细节

可持久化数组实现

可以使用可持久化线段树或可持久化平衡树。

对于并查集，每个元素只有两个属性（父节点和深度），可以使用两个可持久化数组：

1. fa_versions[t][i]：版本t时元素i的父节点
2. dep_versions[t][i]：版本t时元素i所在集合的深度

内存优化

• 每次合并只修改少量元素（1-2个），所以可持久化数组的修改很小
• 使用动态开点的可持久化线段树

示例详细过程（输入样例）

初始版本（版本0）

• fa[0] = [1,2,3,4,5]（每个元素的父节点是自己）
• dep[0] = [1,1,1,1,1]（每个集合深度为1）
• lastans = 0

操作1：合并1和2（创建版本1）

• 查找1的根：1
• 查找2的根：2
• 合并：将2的父节点设为1
• 更新深度：深度不变
• fa[1] = [1,1,3,4,5]
• dep[1] = [2,1,1,1,1]（集合{1,2}深度为2）
• 当前版本 = 1

操作2：查询1和2（版本1）

• 解密：a=1⊕0=1, b=2⊕0=2
• 查找1的根：1
• 查找2的根：1（2→1）
• 相同，输出1
• lastans = 1

操作3：回到版本k（解密k=0）

• 回到版本0（初始状态）
• 当前版本 = 0

操作4：查询0和3（解密a=1, b=2）

• 在版本0中查询1和2
• 查找1的根：1
• 查找2的根：2
• 不同，输出0
• lastans = 0

操作5：回到版本k=1

• 回到版本1（操作1后的状态）
• 当前版本 = 1

操作6：查询1和2（解密a=1, b=2）

• 在版本1中查询1和2
• 相同，输出1
• lastans = 1

数据范围分析

• $n, m \le 2 \times 10^5$
• 每个操作创建一个新版本，最多 $2 \times 10^5$ 个版本
• 可持久化数据结构需要 $O(m \log n)$ 空间

注意事项

1. 强制在线解密：只有在操作类型2和3中才需要解密参数
2. 版本编号：操作编号从1开始，但版本从0（初始状态）开始
3. 按秩合并：确保树的高度为 $O(\log n)$
4. 没有路径压缩：否则无法回退

时空限制

• 时间限制：2秒
• 空间限制：256MB