BZOJ 3673: 可持久化并查集（可持久化并查集+启发式合并）

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn = *+;

 int n,m,tot;

 int t[maxn*],h[maxn*];

 struct node

 {

     int l,r,fa;

 }a[maxn*];

 int build(int l, int r)

 {

     int root = ++tot;

     if(l==r)  {a[root].fa = l;return root;}

     int mid = (l+r)>>;

     a[root].l = build(l,mid);

     a[root].r = build(mid+,r);

     return root;

 }

 int query(int root, int x, int l, int r)

 {

     if(l==r)  return root;

     int mid = (l+r)>>;

     if(x<=mid)  return query(a[root].l,x,l,mid);

     else return query(a[root].r,x,mid+,r);

 }

 int finds(int root, int x)

 {

     int p = query(root,x,,n);

     if(x == a[p].fa)  return p;

     else return finds(root,a[p].fa);

 }

 int modify(int pre, int x, int y, int l, int r)

 {

     int root = ++tot;

     if(l==r)

     {

         a[root].fa = y;

         h[root] = h[pre]; //这个不能忘

         return root;

     }

     a[root].l = a[pre].l, a[root].r = a[pre].r;

     int mid = (l+r)>>;

     if(x<=mid)  a[root].l = modify(a[pre].l, x, y, l, mid);

     else a[root].r = modify(a[pre].r, x, y, mid+, r);

     return root;

 }

 void update(int root, int x, int l, int r)

 {

     if(l==r)  {h[root]++;return;}

     int mid = (l+r)>>;

     if(x<=mid)  update(a[root].l,x, l, mid);

     else update(a[root].r,x, mid+, r);

 }

 void unions(int x, int y, int i)

 {

     if(h[x]>h[y]) swap(x,y);

     t[i] = modify(t[i-],a[x].fa,a[y].fa,,n);  //因为上面的交换，所以这里用fa

     if(h[x]==h[y])  update(t[i],a[y].fa,,n);  //如果深度相等，则插入后深度会+1

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     scanf("%d%d",&n,&m);

     tot = ;

     t[] = build(,n);

     for(int i=;i<=m;i++)

     {

         int op;

         scanf("%d",&op);

         if(op==)

         {

             int aa,bb;

             scanf("%d%d",&aa,&bb);

             t[i] = t[i-];

             int x = finds(t[i],aa);

             int y = finds(t[i],bb);

             if(a[x].fa != a[y].fa)  unions(x,y,i);

         }

         if(op==)

         {

             int aa;

             scanf("%d",&aa);

             t[i] = t[aa];

         }

         if(op==)

         {

             int aa,bb;

             scanf("%d%d",&aa,&bb);

             t[i] = t[i-];

             int x = finds(t[i],aa);

             int y = finds(t[i],bb);

             if(a[x].fa == a[y].fa)  puts("");

             else puts("");

         }

     }

     return ;

 }