题解 P3402 【【模板】可持久化并查集】

· · 个人记录

首先我感觉其他的题解都或多或少出现了一些小问题，这里来发一篇比较正确的题解。
首先可持久化并查集我们是用主席树来维护的，维护\text{2}个量:每个点的父亲和每棵树的根节点的高度。 那么不使用路径压缩的话这个版本的主席树和上个版本的主席树有且只有一个点会被改动。
那么就可以进行可持久化了。
既然取消了路径压缩，为了保证复杂度，我们需要进行按秩合并。
按秩合并其实就是，我们以树高为秩，每次将树高低的树合并到树高高的树上，那么对于树高高的树来说树高并没有变（也就说原树访问根节点的代价并没有变），而树高低的树访问根节点的代价只增加了\text{1}（这棵树的根节点变成了树高高的树的儿子）。
还有一种特殊情况那就是两棵树树高相同。这个时候把树\text{A}合并到树\text{B}上\text{B}的树高会增加\text{1}，而树\text{A}的高度则不会改变。
所以只需要改动一个点，并不是@TPLY所说的改动一群点（他的代码里写的也是只改一个点的代码，自相矛盾）。
也不是@pengym所说的不可能有\text{2}个点深度一样。
（由于一开始写代码的时候没理解清楚，变量名有些混乱，rta,rtb其实是a点和b点在主席树里的编号，depth指的是树高）。 

#include <bits/stdc++.h>

const int N = 1e5 + 10;             
int n, m, i, j, k, cntu;  
int fa[N << 7], depth[N << 7], root[N << 1], lc[N << 7], rc[N << 7];   
int build(int l, int r) {
  int u = ++cntu;
  if (l == r) { fa[u] = l; return u; }
  int mid = (l + r) >> 1;
  lc[u] = build(l, mid);
  rc[u] = build(mid + 1, r);  
  return u;     
}
int query(int u, int l, int r, int x) {
  if (l == r) return u;     
  int mid = (l + r) >> 1;
  if (x <= mid) return query(lc[u], l, mid, x);
  else return query(rc[u], mid + 1, r, x);
}
int update(int pre, int x, int y, int l, int r) {
  int u = ++cntu; lc[u] = lc[pre], rc[u] = rc[pre];      
  if (l == r) {
    fa[u] = y; 
    depth[u] = depth[pre];
    return u;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) lc[u] = update(lc[pre], x, y, l, mid);
  else rc[u] = update(rc[pre], x, y, mid + 1, r);      
  return u;               
}
void add(int u, int l, int r, int x) {
  if (l == r) { depth[u]++; return; }
  int mid = (l + r) >> 1;
  if (x <= mid) add(lc[u], l, mid, x);
  else add(rc[u], mid + 1, r, x);  
}
int find(int v, int x) {
  int y = query(root[v], 1, n, x);         
  if (fa[y] == x) return y;             
  return find(v, fa[y]);      
}

int main() {
  scanf("%d %d", &n, &m);
  root[0] = build(1, n);
  for (int i = 1, op, a, b, v; i <= m; i++) {
    scanf("%d", &op), root[i] = root[i - 1];
    if (op == 1) {
      scanf("%d %d", &a, &b);
      int rta = find(i, a), rtb = find(i, b);       
      if (depth[rta] > depth[rtb]) std::swap(rta, rtb);
      if (fa[rta] == fa[rtb]) continue;
      root[i] = update(root[i - 1], fa[rta], fa[rtb], 1, n);  
      if (depth[rta] == depth[rtb]) add(root[i], 1, n, fa[rtb]);     
    } else if (op == 2) scanf("%d", &v), root[i] = root[v];
    else {
      scanf("%d %d", &a, &b);
      int rta = find(i, a), rtb = find(i, b);  
      puts(fa[rta] == fa[rtb] ? "1" : "0");
    }
  }
  return 0;   
}