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

pengym · 2018-08-08 00:04:57 · 题解

可持久化并查集

洛谷模板

如果想要观看效果更佳，可以点击进入peng-ym's blog查看关于可持久化并查集的详细介绍哟~~ （PS:本文略作删减，只留下可持久化并查集的部分）

前言

• 听名字像是一个十分高端的东西，在今年NOI2018之前，我从未想过自己会用这个数据结构
• 然而，当发现Day1 T1用可持久化并查集可以暴力A的时候，心中无尽的无奈......（毕竟不会）
• 考完后了解了一下，发现似乎是一个挺好理解的数据结构。
• 所以就写了这篇学习笔记！

前置技能

• 可持久化并查集，所需要知道的前置技能很显然！

• 顾名思义，可持久化并查集=可持久化+并查集=可持久化数组+并查集=主席树+并查集！

• 因此，我们首先要会主席树和并查集。

• 可持久化数组这个没什么好说的，就那几个操作，详情见洛谷可持久化数组模板

• 并查集倒是要提一下！

• 并查集中有几种合并方式：

• 一种是直接暴力连父亲（这显然用不上）；

• 一种是路径压缩的合并（这个在普通并查集中很常用，但是好像无法在可持久化并查集中用，听说是可以构造数据使可持久化并查集的空间爆掉？）；

• 还有一种是按秩合并，也就是可持久化并查集中常用的合并方式！其实也就是一种类似于启发式合并的方式，每一次合并时选择一个深度小的点向深度大的合并。这样就可以保证并查集的高度不会增长的太快，保证高度尽量均衡。

步入正题——可持久化并查集

• 其实我们可以发现看懂了前置技能后，可持久化并查集已经不难实现。
• 可持久化并查集其实就是指的用可持久化数组维护并查集中的Fa与按秩合并所需要的dep
• 所谓可持久化并查集，可以进行的操作就只有几个：

1. 回到历史版本（不然怎么叫可持久化呢2333）
2. 合并两个集合（毕竟还是个并查集么）
3. 查询节点所在集合的祖先，当然，因此也可以判断是否在同一个集合中！

• 对于1操作，我们可以很轻松的利用可持久化数组实现。就直接把当前版本的根节点定为第k个版本的根节点就行了！
• 至于代码实现？

  root[i]=root[x];
  //是不是很简单呀！

• 对于2操作，其实也就是按照我在前置技能中所说的按秩合并！
• 对于3操作，也就是在可持久化数组中查询！
• 这样说肯定会有点懵圈，不如一个个函数的解释！

  #define Mid ((l+r)>>1)
  #define lson L[rt],l,Mid
  #define rson R[rt],Mid+1,r
  // 整个代码的三个宏定义

  初始化建树

  void build(int &rt,int l,int r)
  {
      rt=++cnt;
      if(l==r){fa[rt]=l;return ;}
      build(lson);build(rson);
  }
  // 就是普通的可持久化数组构建法，不过维护的是Fa而已

  合并

  void merge(int last,int &rt,int l,int r,int pos,int Fa)
  {
      rt=++cnt;L[rt]=L[last],R[rt]=R[last]; 
      if(l==r)
      {
          fa[rt]=Fa;
          dep[rt]=dep[last];//继承上个版本的值
          return ;
      }
      if(pos<=Mid)merge(L[last],lson,pos,Fa);
      else merge(R[last],rson,pos,Fa);
  }
  // 这个就是单纯的将一个点合并到另一个点上的可持久化数组操作！

  修改节点深度(方便按秩合并)

  void update(int rt,int l,int r,int pos)
  {
      if(l==r){dep[rt]++;return ;}
      if(pos<=Mid)update(lson,pos);
      else update(rson,pos);
  }
  // 可持久化数组普通操作
  // 可能有人会问为什么修改节点深度的时候不需要新开节点！
  // 其实新开节点是根据我们的需要来的！
  // 如果我们需要某个值在某个版本的信息，那么，每当这个值进行修改的时候，我们都需要新添加一个节点，使得我们可以查到各个版本的值
  // 然而dep我们并不需要知道它以前的值是多少，我们只需要用它当前的值去合并就行了！

  查询某一个值所在可持久化数组中的下标

  int query(int rt,int l,int r,int pos)
  {
      if(l==r)return rt;
      if(pos<=Mid)return query(lson,pos);
      else return query(rson,pos);
  }
  // 为了找祖先的操作

  查找祖先

  int find(int rt,int pos)
  {
      int now=query(rt,1,n,pos);
      if(fa[now]==pos)return now;
      return find(rt,fa[now]);
  }
  // 暴力找祖先

• 以上操作就是可持久化并查集的基础函数 单次操作复杂度均为log级的，空间需要注意，也要开n*log级，一般就正常空间乘上40左右吧。
• 合并与查询操作就和普通并查集差不多，只是需要注意当前查询的版本是什么就可以了。
• 当然还需要注意一点，每一次操作都要先把上个版本给传递过来root[i]=root[i-1]
• 放个代码看看吧！
• 按秩合并

  posx=find(root[i],x);posy=find(root[i],y);
  if(fa[posx]!=fa[posy])
  {
      if(dep[posx]>dep[posy])swap(posx,posy);
      merge(root[i-1],root[i],1,n,fa[posx],fa[posy]);
      if(dep[posx]==dep[posy])update(root[i],1,n,fa[posy]);
      // 因为不可能出现深度相同的两个点，所以要把其中一个点深度+1，由于是深度小的合到深度大的上，所以把深度小的增加深度
  }

• 查找

  posx=find(root[i],x);posy=find(root[i],y);
  if(fa[posx]==fa[posy])puts("1");
  else puts("0");
  // 这个真和普通并查集没区别，只是需要注意是什么版本的并查集...

• 至此，可持久化并查集的所有操作就已经解释完了！（相信聪明的你一定可以实现它）

其实，把上面的操作拼起来就是完整代码，不过我还是粘一个完整版吧！

#include<bits/stdc++.h>
#define N 301000
using namespace std;
template<typename T>inline void read(T &x)
{
    x=0;
    static int p;p=1;
    static char c;c=getchar();
    while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
    x*=p;
}
int n,m;
int L[N*30],R[N*30],fa[N*30],dep[N*30];
int root[N*30];
namespace Persistant_Union_Set
{
#define Mid ((l+r)>>1)
#define lson L[rt],l,Mid
#define rson R[rt],Mid+1,r
    int cnt;
    void build(int &rt,int l,int r)
    {
        rt=++cnt;
        if(l==r){fa[rt]=l;return ;}
        build(lson);build(rson);
    }
    void merge(int last,int &rt,int l,int r,int pos,int Fa)
    {
        rt=++cnt;L[rt]=L[last],R[rt]=R[last];
        if(l==r)
        {
            fa[rt]=Fa;
            dep[rt]=dep[last];
            return ;
        }
        if(pos<=Mid)merge(L[last],lson,pos,Fa);
        else merge(R[last],rson,pos,Fa);
    }
    void update(int rt,int l,int r,int pos)
    {
        if(l==r){dep[rt]++;return ;}
        if(pos<=Mid)update(lson,pos);
        else update(rson,pos);
    }
    int query(int rt,int l,int r,int pos)
    {
        if(l==r)return rt;
        if(pos<=Mid)return query(lson,pos);
        else return query(rson,pos);
    }
    int find(int rt,int pos)
    {
        int now=query(rt,1,n,pos);
        if(fa[now]==pos)return now;
        return find(rt,fa[now]);
    }
#undef Mid
#undef lson
#undef rson
}
using namespace Persistant_Union_Set;
int main()
{
    read(n);read(m);
    build(root[0],1,n);
    for(int i=1;i<=m;i++)
    {
        static int opt,x,y;
        read(opt);read(x);
        if(opt==1)
        {
            read(y);
            static int posx,posy;
            root[i]=root[i-1];
            posx=find(root[i],x);posy=find(root[i],y);
            if(fa[posx]!=fa[posy])
            {
                if(dep[posx]>dep[posy])swap(posx,posy);
                merge(root[i-1],root[i],1,n,fa[posx],fa[posy]);
                if(dep[posx]==dep[posy])update(root[i],1,n,fa[posy]);
            }
        }
        else if(opt==2)root[i]=root[x];
        else if(opt==3)
        {
            read(y);
            root[i]=root[i-1];
            static int posx,posy;
            posx=find(root[i],x);posy=find(root[i],y);
            if(fa[posx]==fa[posy])puts("1");
            else puts("0");
        }
    }
    return 0;
}