bzoj 3674(可持久化并查集)
程序员文章站
2024-03-03 17:49:28
...
题解:一道可持久化并查集的裸题,板子子对了就能过;
可持久化并查集是基于主席数的一种结构,可持久化并查集要求能够访问历史版本,跟主席树很像,所以可以通过主席树维护普通并查集的fa数组,但是由于用主席树维护后没有办法用路径压缩,所以需要采用新的合并方式——启发式合并,对每一个节点增加一个level,每次合并从小的指向大的,如果合并的两个节点的level相等,则合并后的节点的level需要增加,据传说与路径压缩的复杂度相同;
AC代码:
#include<stdio.h>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn=2e5+5;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
struct node{
int lson,rson,fa,level;
};
node tree[maxn*20];
int ti[maxn],tot,n,m;//ti记录版本的首节点
inline int build(int l,int r){
int now=++tot;
if(!(l^r)){
tree[now].fa=l;
return now;
}
int mid=(l+r)>>1;
tree[now].lson=build(l,mid);
tree[now].rson=build(mid+1,r);
return now;
}//建树
inline int newpoint(int lst,int l,int r,int x,int fa){
int now=++tot;
int mid=(l+r)>>1;
if(!(l^r)){
tree[now].fa=fa;
tree[now].level=tree[lst].level;
return now;
}
tree[now].lson=tree[lst].lson;
tree[now].rson=tree[lst].rson;
if(x<=mid)
tree[now].lson=newpoint(tree[lst].lson,l,mid,x,fa);
else
tree[now].rson=newpoint(tree[lst].rson,mid+1,r,x,fa);
return now;
}//更新节点
inline void add_level(int now,int l,int r,int x){
//printf("%d %d %d %d %d %d\n",now,l,r,x,tree[now].lson,tree[now].rson);
int mid=(l+r)>>1;
if(!(l^r)){
tree[now].level+=1;
return ;
}
if(x<=mid)
add_level(tree[now].lson,l,mid,x);
else
add_level(tree[now].rson,mid+1,r,x);
}//增加level
inline int query(int now,int l,int r,int x){
int mid=(l+r)>>1;
if(!(l^r))
return now;
if(x<=mid)
return query(tree[now].lson,l,mid,x);
else
return query(tree[now].rson,mid+1,r,x);
}//查询当前版本x所在位置
inline int getfa(int now,int x){
int fa=query(now,1,n,x);
//printf("%d %d %d\n",fa,tree[fa].fa,x);
if(!(tree[fa].fa^x))
return fa;
else
return getfa(now,tree[fa].fa);
}//得到当前版本x父亲的节点位置
inline void connect(int &t,int x,int y){
int fx=getfa(ti[t],x),fy=getfa(ti[t],y);
//printf("%d %d\n",fx,fy);
if(fx==fy)
return ;
if(tree[fx].level<tree[fy].level)
swap(fx,fy);
ti[t]=tot+1;
newpoint(ti[t-1],1,n,tree[fy].fa,tree[fx].fa);
//printf("%d %d\n",ti[t],tot);
if(tree[fx].level==tree[fy].level)
add_level(ti[t],1,n,tree[fx].fa);
}//合并两个联通块
int main( )
{
n=read(),m=read();
int last=0;
ti[0]=1;
tot=0;
build(1,n);
int i,j,k;
for(int t=1;t<=m;t++){
k=read();
if(k==1){
ti[t]=ti[t-1];
i=read()^last,j=read()^last;
connect(t,i,j);
}
else if(k==2){
i=read()^last;
ti[t]=ti[i];
}
else{
ti[t]=ti[t-1];
i=read()^last,j=read()^last;
int fi=getfa(ti[t],i),fj=getfa(ti[t],j);
//printf("%d %d %d %d\n",fi,fj,ti[t],last);
if(tree[fi].fa==tree[fj].fa)
last=1;
else
last=0;
printf("%d\n",last);
}
}
}