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

一只小兵 · 2019-08-02 11:49:01 · 题解

第一篇题解,不好请见谅

思路

可持久化并查集的模板，可持久化想到主席树，并查集想到按秩合并和路径压缩

主席树部分

1. 主席树又称为可持久化线段树，可以维护各个历史版本上的节点。对于不同的的历史版本，新建一个根节点进行维护和查找。
2. 对于任意一个版本，建立一个根节点。在需要查询时，便查找相应的根节点。
3. 如果对每个版本都新建一棵树，那么时间和空间一定是不够的。那么何不考虑在在原有的节点基础上建一棵树呢？
4. 对区间中的一个值进行修改时，新建一个根节点，只对跟修改点相关的点进行修改。

   用图来表示主席树点的修改

   最初的线段树

   修改三号节点后

可见，对于每一次修改，最多会建立 logN 个节点，对于每一次查询，也是 logN （线段树区间查询）

按秩合并并查集部分

1. 对于两个需要相连接的点，将他们的父节点按照大小深度相连接（小联大）。
2. 对于每个点,向上寻找到他的父节点,父节点相同就可以判断两个元素是否在一个集合之中.

   用图表示按秩合并

对于所有集合的合并，深度浅的始终会被并入深度深的，每个集合（树）的深度最多不会超过logn，即可以在logn内找到父节点

在理解了上面两个概念后就可以开始做这道题了

综合

维护一个按秩合并并查集的数组，每次合并操作可以当做是对深度小的节点的父节点的父节点进行修改（有点拗口），那么就可以维护各个版本的集合.

1. 对节点的定义

   struct point{
   int l,r;//左(右)区级
   int son1,son2;//左(右)儿子
   int f,deep;//父节点的标号,和深度
   }p[maxn<<5];

2. 对并查集进行初始化(建立最初的主席树)

   void make_new(int now){
   if(p[now].l == p[now].r) p[now].f=p[now].l,p[now].deep=1;//找到节点,最初父节点为自己,深度为1
   else {
   int mid = (p[now].l+p[now].r)>>1;
   p[++cnt].l=p[now].l;p[cnt].r=mid;p[now].son1=cnt;//左子树
   make_new(p[now].son1);
   p[++cnt].l=mid+1;p[cnt].r = p[now].r;p[now].son2=cnt;//右子树
   make_new(p[now].son2);
   }
   }

3. 查询操作

   int find_f(int x,int now){//x 为查找值，now为当前历史版本跟节点
   int p1 = find_place(x,now);//寻找值在当前节点的位置
   if(p[p1].f == x)//父节点为自己便返回
   return p1;
   return find_f(p[p1].f,now);
   }

4. 连接操作(主要部分)

   void con(int a,int b,int now){//a,b为元素,now为当前历史版本的根节点
   int p1 = find_place(a,now),p2 = find_place(b,now);//a,b在当前树中的位置
   int f1 = find_f(p[p1].l,now),f2 = find_f(p[p2].l,now);查找a,b的父节点
   if(p[f1].deep > p[f2].deep){//深度小的连接到深度大的
   find_new(p[f2].l,now);//注意是新建一个子树进行修改,不然会影响到其他节点
   f2 = cnt;
   p[f2].f = p[f1].l;//注意父节点保存标号
   p[f1].deep += p[f2].deep;
   }
   else {
   find_new(p[f1].l,now);
   f1 = cnt;
   p[f1].f = p[f2].l;
   p[f2].deep += p[f1].deep;
   }
   }

5. 回溯操作

   int k = read();
   p[++cnt] = p[head[k]];head[t] = cnt;//注意回溯是算做一个需要被查询的操作
   now_h = head[t];//将当前历史版本更改

   附上AC代码

   #include <iostream>
   #include <cstdio>
   using namespace std;
   const int maxn = 2e5+17;
   struct point{
   int l,r;//左(右)区间 
   int son1,son2;//左(右)儿子 
   int f,deep;//父节点的标号,和深度 
   }p[maxn<<5];
   long long read(){
   char ch = getchar();
   bool flag = true;
   while(ch < '0' || ch > '9') {
       if(ch == '-') flag = false;
       ch = getchar();
   }
   long long k = ch -'0';
   while(ch = getchar(), ch <= '9' && ch >= '0') {
       k = (k<<1)+(k<<3);
       k += (ch-'0');
   }
   if(flag) return k;
   return -k;
   }
   int cnt,head[maxn];//head储存每个历史版本的根节点 ，cnt为当前节点 
   void make_new(int now){//对并查集的初始化 
   if(p[now].l == p[now].r) p[now].f=p[now].l,p[now].deep=1;
   else {
       int mid = (p[now].l+p[now].r)>>1;
       p[++cnt].l=p[now].l;p[cnt].r=mid;p[now].son1=cnt;
       make_new(p[now].son1);
       p[++cnt].l=mid+1;p[cnt].r = p[now].r;p[now].son2=cnt;
       make_new(p[now].son2);
   }
   }
   int find_place(int num,int now){//对数值在树内位置的查找 num-数,now数的节点 
   if(p[now].l == num && p[now].r == num) return now;
   int mid=(p[now].l+p[now].r)>>1;
   if(num > mid) return find_place(num,p[now].son2);
   else return find_place(num,p[now].son1);
   }
   int find_f(int x,int now){//查找父节点 
   int p1 = find_place(x,now);
   if(p[p1].f == x)
       return p1;
   return find_f(p[p1].f,now);
   }
   void find_new(int num,int now){//对当前值的更新(新建一个子树) 
   if(p[now].l == p[now].r) return;
   int mid = (p[now].l+p[now].r)>>1;
   if(num > mid){//只更新一个子树 
       p[++cnt] = p[p[now].son2];
       p[now].son2 = cnt; 
   //      p[now].f = cnt;
       find_new(num,p[now].son2);
       return;
   }
   else {
       p[++cnt] = p[p[now].son1];
       p[now].son1 = cnt;
   //      p[now].f = cnt;
       find_new(num,p[now].son1);
       return;
   }
   }
   void con(int a,int b,int now){//连接操作 
   int p1 = find_place(a,now),p2 = find_place(b,now);
   int f1 = find_f(p[p1].l,now),f2 = find_f(p[p2].l,now);
   if(p[f1].deep > p[f2].deep){
       find_new(p[f2].l,now);
       f2 = cnt;
       p[f2].f = p[f1].l;
       p[f1].deep += p[f2].deep;
   }
   else {
       find_new(p[f1].l,now);
       f1 = cnt;
       p[f1].f = p[f2].l;
       p[f2].deep += p[f1].deep;
   }
   }
   int main(){
   int n=read(),m=read();
   p[++cnt].l=1;p[cnt].r=n;head[0] = cnt;
   make_new(head[0]);
   int now_h=head[0];//now_h表示当前历史版本的根节点 
   for(int t = 1 ; t <= m ; t++){
       int opt = read();
       if(opt == 1){
           int a=read(),b=read();
           p[++cnt] = p[now_h];head[t] = cnt;//存储当前的历史版本 
           now_h = head[t];
           con(a,b,now_h);
       }
       else if(opt == 2){
           int k = read();
           p[++cnt] = p[head[k]];head[t] = cnt;//注意回溯也需要单独存储 
           now_h = head[t];
       }
       else {
           int a=read(),b=read();
           p[++cnt] = p[now_h];head[t]=cnt;
           now_h = head[t];
           if(p[find_f(a,now_h)].l == p[find_f(b,now_h)].l) printf("1\n");
           else printf("0\n");
       }
   }
   return 0;
   }

注意

1. 每个节点存储的父节点是一个数字，而不是父节点的位置
2. 存储版本后,一定是在当前版本进行修改