洛谷P3402 题解

题目链接

\(Solution:\)

我们使用可持久化数组来维护\(x\)与\(fa\)的关系
但是朴素的算法会\(TLE\)
所以我们考虑按秩合并，使得树高降到\(logn\)级别

\(Code:\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+50;
ll n,m,len,a[N<<5],tmp,pre[N<<5],rt[N<<5],tot;
struct segtree
{
    ll ls,rs,fa,dep;
}tree[N<<5];            
inline ll read()
{
    ll sum=0,f=1;
    char ch=0;
    while(!isdigit(ch))
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        sum=(sum<<1)+(sum<<3)+(ch^48);
        ch=getchar();
    }
    return sum*f;
}
inline void build(ll &t,ll l,ll r)
{
    t=++tot;
    if(l==r)
    {
        tree[t].fa=l;
        return ;
    }
    ll mid=(l+r)>>1;
    build(tree[t].ls,l,mid);
    build(tree[t].rs,mid+1,r);
}
inline void merge(ll lst,ll &x,ll l,ll r,ll pos,ll f)
{
    x=++tot;
    tree[x].ls=tree[lst].ls;
    tree[x].rs=tree[lst].rs;
    if(l==r)
    {
        tree[x].fa=f;
        tree[x].dep=tree[lst].dep;
        return ;
    }
    ll mid=(l+r)>>1;
    if(pos<=mid) merge(tree[lst].ls,tree[x].ls,l,mid,pos,f);
    else merge(tree[lst].rs,tree[x].rs,mid+1,r,pos,f);
}
inline void update(ll x,ll l,ll r,ll pos)
{
    if(l==r)
    {
        tree[x].dep++;
        return ;
    } 
    ll mid=(l+r)>>1;
    if(pos<=mid) update(tree[x].ls,l,mid,pos);
    else update(tree[x].rs,mid+1,r,pos);
}
inline ll query(ll x,ll l,ll r,ll pos)
{
    if(l==r) return x;
    ll mid=(l+r)>>1;
    if(pos<=mid) return query(tree[x].ls,l,mid,pos);
    return query(tree[x].rs,mid+1,r,pos);
}
inline ll find(ll x,ll pos)
{
    ll now=query(x,1,n,pos);
    if(tree[now].fa==pos) return now;
    else return find(x,tree[now].fa);
}
int main(void)
{
    n=read(),m=read();
    build(rt[0],1,n);
    for(register ll i=1;i<=m;i++)
    {
        ll op=read(),x=read();
        if(op==1)
        {
            ll y=read();
            rt[i]=rt[i-1];
            ll f1=find(rt[i],x),f2=find(rt[i],y);
            //printf("%d %d\n",f1,f2);
            if(tree[f1].fa!=tree[f2].fa) 
            {
                if(tree[f1].dep>tree[f2].dep) swap(f1,f2);
                merge(rt[i-1],rt[i],1,n,tree[f1].fa,tree[f2].fa);
                if(tree[f1].dep==tree[f2].dep) update(rt[i],1,n,tree[f2].fa);
            }
        }
        else if(op==2)
        {
            rt[i]=rt[x];
        }
        else if(op==3)
        {
            ll y=read();
            rt[i]=rt[i-1];
            ll f1=find(rt[i],x),f2=find(rt[i],y);
            //printf("%d %d\n",f1,f2);
            if(tree[f1].fa==tree[f2].fa) puts("1");
            else puts("0");
        }
    }
    return 0;
}

洛谷P3402 题解

原文：https://www.cnblogs.com/lgj-lgj/p/12334833.html