BZOJ 3673: 可持久化并查集 by zky

Description

n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

0<n,m<=2∗104

Sample Input

5 6

1 1 2

3 1 2

2 0

3 1 2

2 1

3 1 2

Sample Output

1

0

1

Solution

• 这可以用可持久化线段树维护可持久化并查集。

• 但这里我用的是 rope 大法（rope 适用于大量、冗长的串操作）。

Code

#include<cstdio>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
const int N=2e4+1;
int a[N];
rope<int>*f[N];
inline int read()
{
    int X=0,w=1; char ch=0;
    while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
inline int get(int x,int y)
{
    if(f[x]->at(y)==0) return y;
    f[x]->replace(y,get(x,f[x]->at(y)));
    return f[x]->at(y);
}
int main()
{
    int n=read(),m=read();
    f[0]=new rope<int>(a,a+1+n);
    for(int i=1;i<=m;i++)
    {
        f[i]=new rope<int>(*f[i-1]);
        int type=read();
        if(type==1)
        {
            int x=get(i,read()),y=get(i,read());
            if(x!=y) f[i]->replace(x,y);
        }else
        if(type==2) f[i]=f[read()]; else
            putchar((get(i,read())==get(i,read()))+'0'),putchar('\n');
    }
    return 0;
}