【2017-7-11】BZOJ3673 可持久化并查集

原题:

 可持久化并查集

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

        无语了,第一次接触可持久化数据结构，好端端一个并查集写了一天。

主要问题出在可持久化线段树上面。要注意初值设置和插入函数不能出错，否则答案特别奇葩.

贴一段小小的代码

#include<cstdio> using namespace std; const int maxn=2e4+100; namespace Segtree{ struct node { int l,r,ch[2],fa; }tree[maxn*100]; int cnt=0; int root[maxn],rtcnt=0; void build(int l,int r,int rt){ tree[rt].l=l;tree[rt].r=r; tree[rt].ch[0]=++cnt;tree[rt].ch[1]=++cnt; if(l==r) {tree[rt].fa=l;return;} int mid=(l+r)/2; build(l,mid,tree[rt].ch[0]); build(mid+1,r,tree[rt].ch[1]); } int query(int pos,int rt){ int tl=tree[rt].l,tr=tree[rt].r; if(tl==tr) return tree[rt].fa; int mid=(tl+tr)/2; if(pos<=mid) return query(pos,tree[rt].ch[0]); else return query(pos,tree[rt].ch[1]); } void update(int num,int &rt,int pos){ tree[++cnt]=tree[rt],rt=cnt; int tl=tree[rt].l,tr=tree[rt].r; if(tl==tr) {tree[rt].fa=num;return;} int mid=(tl+tr)/2; if(pos<=mid) update(num,tree[rt].ch[0],pos); else update(num,tree[rt].ch[1],pos); } } namespace comset{ using namespace Segtree; void init(int n){root[0]=rtcnt=cnt=0;build(1,n,0);} int find(int x){ int fa=query(x,root[rtcnt]); if(fa==x) return x; return find(fa); } void combine(int a,int b){ a=find(a),b=find(b); root[rtcnt+1]=root[rtcnt++]; update(b,root[rtcnt],a); } void back(int k){ root[++rtcnt]=root[k]; } } int main(){ using namespace comset; int n,m; scanf("%d%d",&n,&m); init(n); for(int i=1;i<=m;i++){ int opt,a,b; scanf("%d",&opt); if(opt==1) scanf("%d%d",&a,&b),combine(a,b); if(opt==2) scanf("%d",&a),back(a); if(opt==3) scanf("%d%d",&a,&b),root[rtcnt+1]=root[rtcnt++],printf("%d\n",find(a)==find(b)?1:0); } return 0; }