【BZOJ3674】可持久化并查集加强版 （可持久化并查集裸题）

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

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

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

       这么快就口胡完了？好吧，可能是的。但还是有些细节需要注意，可能你们还得不厌其烦地再听一遍“由于本蒟蒻太弱了”这句话（当然这也很真）。对，由于本蒟蒻太弱了，所以我只会写不路径压缩的版本，当然，这就需要启发式合并了。最终，每次找到节点的直接祖先的复杂度为Θ(log n)$\mathrm{\Theta }(logn)$，由于启发式合并，找到集合的根的复杂度为Θ(log2 n)$\mathrm{\Theta }(lo{g}^{2}n)$，总的时间复杂度Θ(m log2 n)$\mathrm{\Theta }(mlo{g}^{2}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;
}