Loading...

洛谷P3402 [模板]可持久化并查集

check评论:0 条 remove_red_eye浏览量:385 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-04-05

可持久化并查集=可持久化+并查集=可持久化数组+并查集=主席树+并查集

主席树维护每个点的父亲再并查集即可,但是这个因为路径压缩会乱套,所以不能路径压缩

然后我随机合并挂了

正确做法是启发式合并吧QAQ,把小的接在大的底下就好qwq

#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
int fa[maxn<<5],rt[maxn],l[maxn<<5],r[maxn<<5],cnt,siz[maxn<<5];
int n,m;
int build(int lf,int rg)
{
    int now=++cnt;
    if(lf==rg)
    {
        fa[now]=lf;
        siz[now]=1;
        return now;
    }
    int mid=(lf+rg)>>1;
    l[now]=build(lf,mid);
    r[now]=build(mid+1,rg);
    return now;
}
void update(int &now,int pre,int lf,int rg,int w,int x)
{
    now=++cnt;
    l[now]=l[pre],r[now]=r[pre];
    if(lf==rg)
    {
        fa[now]=x;
        return ;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        update(l[now],l[pre],lf,mid,w,x);
    }
    else
    {
        update(r[now],r[pre],mid+1,rg,w,x);
    }
}
int query(int pre,int lf,int rg,int x)
{
    if(lf==rg)
    {
        return pre;
    }
    int mid=(lf+rg)>>1;
    if(x<=mid)
    {
        return query(l[pre],lf,mid,x);
    }
    else
    {
        return query(r[pre],mid+1,rg,x);
    }
}
int find(int pre,int x)
{
    int qaq=query(rt[pre],1,n,x);
    if(fa[qaq]==x)
    {
        return qaq;
    }
    return find(pre,fa[qaq]);
}
void un(int pre,int lf,int rg)
{
    int dx=find(pre,lf),dy=find(pre,rg);
    if(fa[dx]!=fa[dy])
    {
        if(siz[fa[dx]]>siz[fa[dy]])
        {
            swap(dx,dy);
        }
        update(rt[pre],rt[pre-1],1,n,fa[dx],fa[dy]);
        siz[fa[dy]]+=siz[fa[dx]];
    }
}
int qu(int pre,int lf,int rg)
{
    int dx=find(pre,lf),dy=find(pre,rg);
    if(fa[dx]==fa[dy])
    {
        return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>m;
    rt[0]=build(1,n);
    int opt,lf,rg;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            rt[i]=rt[i-1];
            scanf("%d%d",&lf,&rg);
            un(i,lf,rg);
        }
        if(opt==2)
        {
            scanf("%d",&lf);
            rt[i]=rt[lf];
        }
        if(opt==3)
        {
            rt[i]=rt[i-1];
            scanf("%d%d",&lf,&rg);
            printf("%d\n",qu(i,lf,rg));
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名