bzoj3673 可持久化并查集

#include<bits/stdc++.h>
using namespace std;
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 20005
#define maxm 3000000
using namespace std;
int n,m,p,x,y,cnt;
int rt[maxn],v[maxm],ls[maxm],rs[maxm];
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<‘0‘||ch>‘9‘){if (ch==‘-‘) f=-1;ch=getchar();}
    while (ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
    return x*f;
}
void build(int &k,int l,int r)
{
    k=++cnt;
    if (l==r)
	  {
	         v[k]=l;
			 return;
	  }
    int mid=(l+r)>>1;
    build(ls[k],l,mid);
	build(rs[k],mid+1,r);
}
int query(int k,int l,int r,int pos)
{
    if (l==r) 
	    return v[k];
    int mid=(l+r)>>1;
    if (pos<=mid)
	    return query(ls[k],l,mid,pos);
    else 
	    return query(rs[k],mid+1,r,pos);
}
void insert(int x,int &y,int l,int r,int pos,int val)
//要实现v[pos]的值改为val
//x是上一个版本的线段树
//y为当前版本的
//pos为位置，val为要设置的值 
{
	cout<<x<<" "<<y<<" "<<l<<" "<<r<<" "<<pos<<" "<<val<<endl;
	char ww;
	cin>>ww;
    y=++cnt;
    cout<<"cnt is   "<<cnt<<endl;
    
    if (l==r)
	{
	   v[y]=val;
	   return;
	}
    int mid=(l+r)>>1;
    ls[y]=ls[x];rs[y]=rs[x];
    if (pos<=mid) 
	    insert(ls[x],ls[y],l,mid,pos,val);
    else 
	    insert(rs[x],rs[y],mid+1,r,pos,val);
}
int find(int &root,int x)
{
    int tmp=query(root,1,n,x); 
    //在第root个线段上找，区间为[x,x]，也就是叶子点了
	//其值为多少 
    if (tmp==x) 
	    return x;
    else
    {
        int ret=find(root,tmp);
         //在当前的线段树上进行查找 
        insert(root,root,1,n,x,ret);
        //并进行修改,x是位置，ret为所要变成的值 
        return ret;
    }
}
int main()
{
    n=read();m=read();
    build(rt[0],1,n);
    F(i,1,m)
    {
    
        p=read();
        if (p==1) //1 a b 合并a,b所在集合
        {
            int x=read(),y=read(),
			fx=find(rt[i-1],x),fy=find(rt[i-1],y);
			
            if (fx==fy) 
			    rt[i]=rt[i-1];
            else 
			     insert(rt[i-1],rt[i],1,n,fx,fy);
	
        }
        else if (p==2) 
		//2 k 回到第k次操作之后的状态(查询算作操作) 
        {
            int x=read();
            rt[i]=rt[x];
        }
        else
        //3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
        {
            int x=read(),y=read(),fx=find(rt[i-1],x),fy=find(rt[i-1],y);
            if (fx==fy) puts("1");
            else puts("0");
            rt[i]=rt[i-1];
        
        }
    }
    return 0;
}
//https://blog.csdn.net/AaronGZK/article/details/51511601