Bzoj 3673: 可持久化并查集 by zky(主席树+启发式合并)

本文主要是介绍Bzoj 3673: 可持久化并查集 by zky(主席树+启发式合并)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

3673: 可持久化并查集 by zky
Time Limit: 5 Sec Memory Limit: 128 MB
Description
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
0<=n,m<=2*10^4
Input
Output
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
HINT
Source
出题人大SB

/*
可持久化线段树+启发式合并. 
可持久化线段树维护当前状态下集合的关系和秩的信息.
所谓的秩就是以该元素为代表元的所有元素中的最大深度.
然后按秩合并的目的是为了降常. 
每个叶节点维护一颗线段树 
合并的时候在权值线段树的子节点加一个数,
相当于连了一条边 表示有关系存在.
要先查询要将合并两个元素的父亲所在位置.
显然只有在两个集合秩相同时才更新秩.
*/
#include<iostream>
#include<cstdio>
#define MAXN 20001
using namespace std;
int n,m,tot,root[MAXN],s[MAXN];
struct data{int lc,rc,deep,x;}tree[MAXN*20];
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-48,ch=getchar();return x*f;
}
void build(int &k,int l,int r)
{k=++tot;if(l==r){tree[k].x=l;return ;}int mid=(l+r)>>1;build(tree[k].lc,l,mid);build(tree[k].rc,mid+1,r);return ;
}
int query(int k,int l,int r,int x)
{if(l==r) return k;int mid=(l+r)>>1;if(x<=mid) return query(tree[k].lc,l,mid,x);else return query(tree[k].rc,mid+1,r,x);
}
int find(int root,int x)
{int p=query(root,1,n,x);if(x==tree[p].x) return p;else return find(root,tree[p].x);
}
void change(int &k,int last,int l,int r,int x,int y)
{k=++tot;tree[k].lc=tree[last].lc,tree[k].rc=tree[last].rc;if(l==r) {tree[k].x=y;tree[k].deep=tree[last].deep;return ;}int mid=(l+r)>>1;if(x<=mid) change(tree[k].lc,tree[last].lc,l,mid,x,y);else change(tree[k].rc,tree[last].rc,mid+1,r,x,y);return ;
}
void updata(int k,int l,int r,int x)
{if(l==r){tree[k].deep++;return ;}int mid=(l+r)>>1;if(x<=mid) updata(tree[k].lc,l,mid,x);else updata(tree[k].rc,mid+1,r,x);return ;
}
void union_s(int l1,int l2,int i)
{if(tree[l1].deep>tree[l2].deep) swap(l1,l2);change(root[i],root[i-1],1,n,tree[l1].x,tree[l2].x);if(tree[l1].deep==tree[l2].deep) updata(root[i],1,n,tree[l2].x);return ;
}
int main()
{int x,y,z,l1,l2;n=read(),m=read();build(root[0],1,n);for(int i=1;i<=m;i++){z=read();if(z==1){x=read(),y=read();root[i]=root[i-1];l1=find(root[i],x),l2=find(root[i],y);if(tree[l1].x!=tree[l2].x) union_s(l1,l2,i);}else if(z==2) x=read(),root[i]=root[x];else {x=read(),y=read();root[i]=root[i-1];l1=find(root[i],x),l2=find(root[i],y);if(l1==l2) printf("1\n");else printf("0\n");}}return 0;
}