分析

要做的其实就是实现一个可持久化数组以及按秩合并。

如何实现可持久化数组？如果每次都复制一遍那肯定时空都不行。想到用二分实现操作，每次只修改一个点，那么可以用类似线段树一样的区间覆盖复制原fa数组满足要求，每次把未变的复制一下，只改变要变的那条树链就行了。而既然与线段树如此类似，我们就直接用一个线段树加一个可持久化线段树就行了。由于是按秩合并，不带路径压缩，所以find查询的时候有两个\(\log\)

时间复杂度\(O(m\log^2n+n\log n)\)，空间复杂度\(O(m\log n+n\log n)\)

代码

#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<complex>
#pragma GCC optimize ("O0")
using namespace std;
template<class T> inline T read(T&x){
    T data=0;
    int w=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch==‘-‘)
            w=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        data=10*data+ch-‘0‘,ch=getchar();
    return x=data*w;
}
typedef long long ll;
const int INF=0x7fffffff;

int n;

struct PreSegTree
{
    int L,R;
    int fa;
    int dep;
}PST[4400000]; // 4321928.0948873623478703194294894
int root[200007],pcnt;

void build(int&now,int l,int r)
{
    if(!now)
        now=++pcnt;
    if(l==r)
    {
        PST[now].fa=l;
//      cerr<<now<<"fa ="<<PST[now].fa<<endl;
        return;
    }
    int mid=(l+r)>>1;
    build(PST[now].L,l,mid);
    build(PST[now].R,mid+1,r);
}

int query(int now,int l,int r,int p)
{

//  cerr<<"querying "<<now<<‘ ‘<<l<<" "<<r<<" "<<p<<endl;
    if(l==r)
        return now;
    int mid=(l+r)>>1;
    if(p<=mid)
        return query(PST[now].L,l,mid,p);
    else if(p>=mid+1)
        return query(PST[now].R,mid+1,r,p);
}

void modify(int&now,int l,int r,int p,int v)
{
    PST[++pcnt]=PST[now],now=pcnt;
    if(l==r)
    {
        PST[now].fa=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
        modify(PST[now].L,l,mid,p,v);
    else if(p>=mid+1)
        modify(PST[now].R,mid+1,r,p,v);
}

void add(int now,int l,int r,int p)
{
//  PST[++pcnt]=PST[now],now=pcnt;
    if(l==r)
    {
        ++PST[now].dep;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
        add(PST[now].L,l,mid,p);
    else if(p>=mid+1)
        add(PST[now].R,mid+1,r,p);
}

int find(int now,int p)
{
    int x=query(now,1,n,p);
//  cerr<<"query="<<x<<" fx="<<PST[x].fa<<" p="<<p<<endl;
    if(PST[x].fa==p)
        return x;
    return find(now,PST[x].fa);
}

int main()
{
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    int m;
    read(n);read(m);
    build(root[0],1,n);
    int ans=0;
    for(int i=1;i<=m;++i)
    {
        int opt;
        read(opt);
        if(opt==1)
        {
            int a,b;
            read(a);read(b);
            a^=ans,b^=ans;
            root[i]=root[i-1];
            int fx=find(root[i],a),fy=find(root[i],b);
//          cerr<<"result="<<fx<<" "<<fy<<endl;
//          cerr<<"fa="<<PST[fx].fa<<" "<<PST[fy].fa<<endl;
            if(PST[fx].fa==PST[fy].fa)
                continue;
            if(PST[fx].dep>PST[fy].dep)
                swap(fx,fy);
            modify(root[i],1,n,PST[fx].fa,PST[fy].fa);
            if(PST[fx].dep==PST[fy].dep)
                add(root[i],1,n,PST[fy].fa);
        }
        else if(opt==2)
        {
            int k;
            read(k);
            k^=ans;
            root[i]=root[k];
        }
        else if(opt==3)
        {
            int a,b;
            read(a);read(b);
            a^=ans,b^=ans;
            root[i]=root[i-1];
            int fx=find(root[i],a),fy=find(root[i],b);
//          cerr<<"result="<<fx<<" "<<fy<<endl;
//          cerr<<"fa="<<PST[fx].fa<<" "<<PST[fy].fa<<endl;
            if(PST[fx].fa==PST[fy].fa)
                ans=1;
            else
                ans=0;
            printf("%d\n",ans);
        }
    }
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

BZOJ3674 可持久化并查集加强版

原文：https://www.cnblogs.com/autoint/p/9529953.html