欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【BZOJ3674】可持久化并查集加强版 (可持久化并查集裸题)

程序员文章站 2024-03-03 19:08:10
...

       又到暑假了,颓了好些天的蒟蒻决定再次开始写博客了。由于本蒟蒻太弱了,连NOI都没资格参加,只好在家里看NOI的同步赛题呜呜呜~。第一题一看就是可持久化并查集裸题,可是蒟蒻没写过。。。所以决定先写道裸题练练手(顺便存板子)。

       当然题目链接也是必不可少的:bzoj3674

       可持久化并查集,听起来很高大上的样子,其实并不是很复杂,我们写普通并查集的时候不就是记一个parent数组吗?可持久化并查集其实也就是建立在可持久化数组上的并查集罢了,可持久化数组也只需用一棵可持久化线段树(主席树)维护就行了。

       这么快就口胡完了?好吧,可能是的。但还是有些细节需要注意,可能你们还得不厌其烦地再听一遍“由于本蒟蒻太弱了”这句话(当然这也很真)。对,由于本蒟蒻太弱了,所以我只会写不路径压缩的版本,当然,这就需要启发式合并了。最终,每次找到节点的直接祖先的复杂度为Θ(log n),由于启发式合并,找到集合的根的复杂度为Θ(log2 n),总的时间复杂度Θ(m log2 n),还是挺优秀的吧。

       模板:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int son[4000010][2],par[4000010],cnt;
void build(int &x,int l,int r)
{
    x=++cnt;
    if(l==r)
    {
        par[x]=l;
        return;
    }
    int mid=(l+r)>>1;
    build(son[x][0],l,mid);
    build(son[x][1],mid+1,r);
}
void update(int &x,int l,int r,int p,int v)
{
    cnt++;
    son[cnt][0]=son[x][0];
    son[cnt][1]=son[x][1];
    x=cnt;
    if(l==r)
    {
        par[x]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)update(son[x][0],l,mid,p,v);
    else update(son[x][1],mid+1,r,p,v);
}
int getpar(int x,int l,int r,int p)
{
    if(l==r)return par[x];
    int mid=(l+r)>>1;
    if(p<=mid)return getpar(son[x][0],l,mid,p);
    else return getpar(son[x][1],mid+1,r,p);
}
int root[200010];
int n,m;
pair<int,int> getrot(int k,int x)
{
    int y;
    int rnk=0;
    while((y=getpar(root[k],1,n,x))!=x)rnk++,x=y;
    return make_pair(x,rnk);
}
int ans;
int main()
{
    scanf("%d%d",&n,&m);
    build(root[0],1,n);
    for(int i=1;i<=m;i++)
    {
        int op;
        scanf("%d",&op);
        if(op==2)
        {
            int k;
            scanf("%d",&k);
            k^=ans;
            root[i]=root[k];
        }
        else
        {
            root[i]=root[i-1];
            int a,b;
            scanf("%d%d",&a,&b);
            a^=ans;b^=ans;
            pair<int,int>ta=getrot(i-1,a),tb=getrot(i-1,b);
            a=ta.first;b=tb.first;
            if(op==1)
            {
                int ra=ta.second,rb=tb.second;
                if(a!=b)
                {
                    if(ra<rb)update(root[i],1,n,a,b);
                    else update(root[i],1,n,b,a);
                }
            }
            else
            {
                if(a==b)ans=1;else ans=0;
                printf("%d\n",ans);
            }
        }
    }
    return 0;
}