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

chenxinyang2006 · 2020-01-23 15:36:45 · 题解

这个东西本身不是很难写，就是把并查集平时用的fa[i]数组可持久化一下就行了

但是由于现在需要可持久化，所以路径压缩这种均摊的方法肯定T飞，我们需要严格每次只访问log_2 n个点的合并方式

• 按树高合并

  每次合并时按照树高合并，将树高小的接在树高大的下面

  显然，如果两棵树的树高不同，合并完以后的树树高不会增加（被接上去的节点深度 + 1，但是高的那棵树的树高，如果与矮的不同，至少比矮的大1，所以没有影响）

  当两棵树树高相同时，合并后的树树高 + 1

  设siz(h)表示这样合并，树高为h的树，最小有siz(h)个节点

  显然，当我们需要一棵树高为h + 1的树时，我们至少需要将两棵树高为h的树合并起来

  也就是说siz(h + 1) \ge 2 \times siz(h)

  边界siz(1) = 1，所以siz(h) = 2 ^ {h - 1}

  我们这样也可以求出h的最大值：

  \because 2 ^ {h - 1} = n \therefore h = log_2 n + 1

  这样就证明了，按树高合并，树高至多log_2 n

• 按size合并

  每次合并时按照子树大小(size)合并，把size小的接在size大的下面

  显然，每次只有被接到下面的子树，深度才会 + 1

  设当前这棵树size为x，高为h_1，有size为y，高为h_2的要与之合并

  若x < y，那么x会被接到y的下面，高变为max(h_1 + 1,h_2)

  • 如果h_2 \ge h_1 + 1，那么实际上毫无影响，对于y来说，树高没有变化

  • 如果h_2 < h_1 + 1，那么树高增加1，但是size变为x + y

  \because y > x \therefore x + y > 2x 若$x > y$，那么$swap(x,y)$（大雾），实际上本情况和上面没有区别 经过一番分类讨论，按$size$合并唯一会增加树高的地方，就是当$h_2 < h_1 + 1$，那么树高增加$1$，但是$size$翻倍 显然，$size$至多翻倍$log_2 n$次，所以树高也是至多$log_2 n

• 为什么随机化合并不对

  总是有人觉得，随机化合并应该不会被hack，因为我合并都是随机的，你怎么卡？

  但是本题的#5真的就卡了随机化合并……

  第5个点的构造方式是：依次将每个和下一个合并

  如果写的是随机合并的话，期望有\frac{n}{2}次将一颗树接到一个点上，所以就会导致树高\frac{n}{2}

  所以，随机化合并不能保证树高的问题，树高甚至会退化为\frac{n}{2}

最后，给出一个按size合并的例子：

#include <cstdio>
#include <cstdlib>
using namespace std;
int n,m,ti;

struct TREE{
    int T[200005],st[200005];//T[i]表示第i次操作后的根,st[i]表示i地方初始值
    int ls[200005 << 5],rs[200005 << 5],val[200005 << 5];//ls[i]是i节点左儿子,rs[i]是i节点右儿子
    int cnt;
    int build(int l,int r){//返回节点编号
        int rt = ++cnt;
        if(l == r){
            val[rt] = st[l];
            return rt;
        }
        int mid = l + r >> 1;
        ls[rt] = build(l,mid);
        rs[rt] = build(mid+1,r);
        return rt;
    }
    int upload(int pt,int l,int r,int id,int C){//pt是原版本这个节点的位置，这个操作是单点赋值
        int rt = ++cnt;
        ls[rt] = ls[pt];
        rs[rt] = rs[pt];

        if(l == r){
            val[rt] = C;
            return rt;
        }
        int mid = l + r >> 1;
        if(id <= mid){
            ls[rt] = upload(ls[pt],l,mid,id,C);
        }else{
            rs[rt] = upload(rs[pt],mid+1,r,id,C);
        }
        return rt;
    }
    int query(int rt,int l,int r,int id){//单点查询
        if(l == r){
            return val[rt];
        }
        int mid = l + r >> 1;
        if(id <= mid){
            return query(ls[rt],l,mid,id);
        }else{
            return query(rs[rt],mid+1,r,id);
        }
    }
}bin,siz;//bin存每个点的father,siz存每个点的size大小

int find(int x){
    while(bin.query(bin.T[ti],1,n,x) != x){//这里就是一直往上跳
        x = bin.query(bin.T[ti],1,n,x);
    }
    return x;
}

void merge(int x,int y){
    int a = find(x);
    int b = find(y);
    if(a == b) return;//自己给自己合并会导致size不正确，特判掉
    int X = siz.query(siz.T[ti],1,n,a),Y = siz.query(siz.T[ti],1,n,b);
    if(X <= Y){//如果a的size比b小，就接到b上
        bin.T[ti] = bin.upload(bin.T[ti],1,n,a,b);//bin[a] = b
        siz.T[ti] = siz.upload(siz.T[ti],1,n,b,X + Y);//注意相加size
    }else{
        bin.T[ti] = bin.upload(bin.T[ti],1,n,b,a);
        siz.T[ti] = siz.upload(siz.T[ti],1,n,a,X + Y);
    }
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        bin.st[i] = i;//一开始，所有点father是自己
    }
    bin.T[0] = bin.build(1,n);
    for(int i = 1;i <= n;i++){
        siz.st[i] = 1;//所有点size为1
    }
    siz.T[0] = siz.build(1,n);

    int opt,x,y;
    for(ti = 1;ti <= m;ti++){
        scanf("%d",&opt);
        bin.T[ti] = bin.T[ti - 1];
        siz.T[ti] = siz.T[ti - 1];//先重置一下，否则可能出锅
        if(opt == 1){
            scanf("%d%d",&x,&y);
            merge(x,y);
        }else if(opt == 2){
            scanf("%d",&x);
            bin.T[ti] = bin.T[x];
            siz.T[ti] = siz.T[x];
        }else{
            scanf("%d%d",&x,&y);
            if(find(x) == find(y)) printf("1\n");
            else printf("0\n");
        }
    }
    return 0;
}

按树高合并的话，只要把merge函数改成这样就行了

void merge(int x,int y){
    int a = find(x);
    int b = find(y);
    if(a == b) return;
    int X = siz.query(siz.T[ti],1,n,a),Y = siz.query(siz.T[ti],1,n,b);
    if(X <= Y){
        bin.T[ti] = bin.upload(bin.T[ti],1,n,a,b);
        if(X == Y) siz.T[ti] = siz.upload(siz.T[ti],1,n,b,X + 1);//只有在树高相同时，新树树高才会 + 1
    }else{
        bin.T[ti] = bin.upload(bin.T[ti],1,n,b,a);
        if(X == Y) siz.T[ti] = siz.upload(siz.T[ti],1,n,a,Y + 1);
    }
}