【模板】可持久化并查集(Persistent DSU)

题目描述

给定 $n$ 个集合，第 $i$ 个集合内初始状态下只有一个数，为 $i$。

有 $m$ 次操作。操作分为 $3$ 种：

• 1 a b 合并 $a,b$ 所在集合；

• 2 k 回到第 $k$ 次操作（执行三种操作中的任意一种都记为一次操作）之后的状态，保证已经进行过至少 $k$ 次操作（不算本次操作），特别的，若 $k=0$，则表示回到初始状态；

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

输入格式

第一行两个整数，$n,m$。

接下来 $m$ 行，每行先输入一个数 $opt$。若 $opt=2$ 则再输入一个整数 $k$，否则再输入两个整数 $a,b$，描述一次操作。

输出格式

对每个操作 $3$，输出一行一个整数表示答案。

样例输入 #1

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

样例输出 #1

1
0
1

数据范围

对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le m\le 2\times 10^5$，$1 \le a, b \le n$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接