P3452 基于线段树的并查集

PCCP · 2023-07-24 21:15:22 · 题解

题解里已经有一篇并查集的题解了，但是并不是我这种做法，所以特来写一篇题解，这样才对得起我调了一个下午的成果。当然了，那位dalao的解法比我的优很多（

思考过程

看到这道题，我们一眼顶真，发现和我们熟悉的P3295 萌萌哒以及P1840 Color the Axis很像啊。

为什么这么说呢，题目给定了我们一些关系，两个人之间有连系就可以把这两个人分开来，但是这两个一定会分开了吗？不一定！考虑下图这么一种情况：

其中点 2 和点 4 有联系，那么可以把他们分开来吗？不可以，因为 3 与 2 和 4 均没有联系。

在此前的诸多题目里，我们应该养成了正反向同时思考的习惯，事物存在对立的这一面，就一定存在对立的另一面。我们考虑建立补图，发现没有联系的两人是必须在同一栋楼里的，不理解的同学请去回顾题意。

我们得到这么一种暴力的做法：建立补图后求连通块数量，图论做法的时间复杂度为 O(n^2-m) ，而并查集做法还要带个反阿克曼函数。以本题的数据范围，这是不可接受的。

我们不免去思考如何优化建图，但是这是和连通块相关的题，放着并查集不想，何必煞费苦心去想优化建图呢！有50块钱的好兄弟填线，要什么T-90（

发现给定关系的数量比较少，考虑把给定关系排序（注意：要求同一点对内第一关键字比第二关键字小，就像普通建图一样）。这样对于同一第一关键字来说，连续的少量的第二关键字把 1 - n 的范围划分成了几个少量的大区间。我们只要维护区间和点之间的连通关系即可。

这样一来就和我们前面说到的两道题有些相似之处了：维护一段区间和一个点的连通关系。

蒟蒻的做法

看到区间问题，想到线段树，一个点即可代表一个区间，符合我们对并查集维护点与点之间的关系的幻想。按以下过程即可通过本题：

• 预处理区间节点，每一个节点的父亲就是他之间的编号；

• 将给定关系排序，划分区间；

• 像修改线段树一样将代表范围区间内的节点与代表原本的一个人的叶子节点合并；

• 结束后，自上而下遍历，对于每一个非叶子节点，如果当前节点被划分到一个不同于本身的集合，那么将两个儿子节点同当前节点合并；

• 最后对于每一个叶子节点，找到其祖宗节点，统计答案即可。

时间复杂度：预期为 O(m\log_2{n}\alpha(n)) ，不是很优，但是仍可以一半左右的时间和四分之一左右的空间通过本题。

正确性

• 在这里，我们建的线段树并不是普通的线段树，我们不需要线段树维护什么，只需要它划分区间，因此并不是一种从属的父子节点的关系，只有包含与被包含的关系，在并查集中一个节点的父亲节点是它本身，而不是线段树里的父亲节点吗，因此不会所有节点一开始就都被连通到一起去。

• 存在一种情况，某区间内存在独立点，而剩下的则有划分：自上而下遍历时，如果一个非叶子结点对应的区间是不完全的，不合并两个子节点即可。

tips:

同时有路径压缩和按秩合并的并查集的时间复杂度才是 O(m\alpha(n)) ，只有路径压缩的并查集， Tarjan 证明其最劣时间复杂度是 O(m\log_2{n}) ，姚期智证明了其平均复杂度是 O(m\alpha(m,n)) ，按秩合并比较难写，可以使用启发式合并代替，时间复杂度和按秩合并是一样，这里不证明了。

实测有启发式合并比没有快了 0.05s :(

具体见代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
const int N=3e5+10;
const int M=3e6+10;
int n,m,fa[M],siz[M],seq[N],maxn,cnt[N];
struct node{
    int x,y;
}p[M];
vector<int> ple[N];
set<int> q;
multiset<int> res;
inline bool cmp(node a,node b){
    if(a.x==b.x){
        return a.y<b.y;
    }
    return a.x<b.x;
}
inline int find(int x){
    //查找root 
    if(fa[x]==x){
        return x;
    }
    return fa[x]=find(fa[x]);
}
inline void hb(int fx,int fy){
    //启发式合并 
    if(siz[fx]<siz[fy]){
        swap(fx,fy);
    }
    siz[fx]+=siz[fy];
    fa[fy]=fx;
}
inline void build(int x,int l,int r){
    //建树 
    maxn=max(maxn,x);
    if(l==r){
        seq[l]=x;
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
}
inline void ycl(){
    //预处理 
    build(1,1,n);
    for(int i=1;i<=maxn;i++){
        fa[i]=i;
        siz[i]=1;
    }
}
inline void unify(int x,int l,int r,int ql,int qr,int k){
    //普通线段树修改式遍历 
    if(ql<=l&&r<=qr){
        int fy=find(x),fx=find(seq[k]);
        //不同才合并，节省时间 
        if(fx!=fy){
            hb(fx,fy);
        }
        return;
    }
    int mid=(l+r)>>1;
    if(ql<=mid){
        unify(x<<1,l,mid,ql,qr,k);
    }
    if(qr>mid){
        unify(x<<1|1,mid+1,r,ql,qr,k);
    }
}
inline void prepare(int x,int l,int r){
    int fx=find(x),fy;
    if(fx!=x&&l!=r){
        fy=find(x<<1);
        if(fy!=fx){
            hb(fx,fy);
        }
        fy=find(x<<1|1);
        if(fy!=fx){
            hb(fx,fy);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    ycl();
    int x,y;
    //输入 
    for(int i=1;i<=m;i++){
        scanf("%d%d",&p[i].x,&p[i].y);
        if(p[i].x>p[i].y){
            swap(p[i].x,p[i].y);
            //保证第一关键字比第二关键字小 
        }
    }
    //排序 
    sort(p+1,p+m+1,cmp);
    for(int i=1;i<=m;i++){
        ple[p[i].x].push_back(p[i].y);
    }
    int l=0,r=0;
    for(int i=1;i<=n;i++){
        int len=ple[i].size();
        l=0;
        if(!len){
            if(i+1<=n){
                unify(1,1,n,i+1,n,i);
            }
            continue;
        }
        for(int j=0;j<len;j++){
            if(j!=0){
                l=ple[i][j-1]+1;
            }
            r=ple[i][j]-1;
            if(r<=i||l>r){
                //不能和比自己小的区间合并，因为第一关键字比第二关键字小，无法确定关系 
                continue;
            }
            if(l<=i){
                //同上 
                l=i+1;
            }
            unify(1,1,n,l,r,i);
        }
        if(ple[i][len-1]+1<=n){
            //小学奥数的植树问题的原理 
            unify(1,1,n,ple[i][len-1]+1,n,i);
        }
    }
    //全树合并 
    prepare(1,1,n);
    for(int i=1;i<=n;i++){
        //一个一个找root 
        x=find(seq[i]);
        q.insert(x);
        cnt[x]++;
    }
    //输出答案 
    y=q.size();
    printf("%d\n",y);
    set<int>::iterator it;
    for(it=q.begin();it!=q.end();it++){
        res.insert(cnt[*it]);
    }
    multiset<int>::iterator item;
    for(item=res.begin();item!=res.end();item++){
        printf("%d ",*item);
    }
}

这么良心的题解，不点个赞再走吗？