Description:


n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0
0<n,m<=2*10^4

Sample Input:


Sample Output:


题解:


才开始做可持久化并查集(其实就是可持久化线段树)
用可持久化线段树维护fa数组,不路径压缩按秩合并就可以了。
这样时间复杂度是 \(O(m\log^2 n)\)

然而开始理解错题意(第二种操作也属于操作),RE了又WA又CE TAT

貌似这个题可以水过去。