正文
BZOJ.3673/3674.可持久化并查集(可持久化线段树 按秩合并/启发式合并)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
BZOJ 3673
BZOJ 3674(加强版)
如果每次操作最多只修改一个点的fa[]，那么我们可以借助可持久化线段树来O(logn)做到。如果不考虑找fa[]的过程，时空复杂度都是O(logn)。
想要这样就不能加路径压缩，否则要对路径上的点都要改，最好时空复杂度是O(log^2n)，但是空间会炸。
合并集合时按秩合并，这样暴力找fa[]的复杂度为O(logn)。
再加上线段树就是O(log^2n)。(当然空间是O(mlogn))
具体：可持久化线段树每个叶子节点储存其fa[x]。每次按秩合并时，在之前树根的基础上新建logn个点，修改对应位置的fa[rt]=new_fa。
按sz启发式合并更好写，而且sz[]还有其它用。3643比按秩合并慢点，3644一样，洛谷上就快些。。
但都是1个log的。
离线做法： 操作的版本能构成一棵树。建出树来DFS，进入一个节点时修改，访问完一个节点时撤销修改。
BZOJ 3673：
//6492kb 36ms
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 600000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=2e4+5,M=2e4+5;
int n,root[M];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Segment_Tree
{
#define S M*16
#define lson son[x][0]
#define rson son[x][1]
int tot,fa[S],dep[S],son[S][2];
void Build(int &x,int l,int r)
{
x=++tot;
if(l==r) fa[x]=l;
else Build(lson,l,l+r>>1),Build(rson,(l+r>>1)+1,r);
}
void Add(int x,int l,int r,int p)//合并两个dep相同的集合时，使没被合并的那个dep+1
{
if(l==r) return (void)++dep[x];
int m=l+r>>1;
p<=m?Add(lson,l,m,p):Add(rson,m+1,r,p);
}
void Modify(int &x,int y,int l,int r,int pos,int v)//重建一遍 将pos处的fa改为v
{
x=++tot;
if(l==r) {fa[x]=v, dep[x]=dep[y]; return;}
int m=l+r>>1;
if(pos<=m) rson=son[y][1], Modify(lson,son[y][0],l,m,pos,v);
else lson=son[y][0], Modify(rson,son[y][1],m+1,r,pos,v);
}
int Query(int x,int l,int r,int pos)
{
if(l==r) return x;//返回树上一个节点(dep是节点的)
int m=l+r>>1;
return pos<=m?Query(lson,l,m,pos):Query(rson,m+1,r,pos);
}
int Get_fa(int rt,int x)
{
int p=Query(rt,1,n,x);//找到fa[p]==x的树上节点p(x是位置...)
return x==fa[p]?p:Get_fa(rt,fa[p]);
}
void Union(int &rt,int x,int y)
{
int p1=Get_fa(rt,x),p2=Get_fa(rt,y);
if(fa[p1]==fa[p2]) return;
if(dep[p1]>dep[p2]) std::swap(p1,p2);//r1->r2
Modify(rt,rt,1,n,fa[p1],fa[p2]);//fa[r1]=r2 -> fa[fa[p1]]=fa[p2]
if(dep[p1]==dep[p2]) Add(rt,1,n,fa[p2]);
}
}T;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
n=read(), T.Build(root[0],1,n);
for(int m=read(),i=1,opt; i<=m; ++i)
{
if((opt=read())==1) root[i]=root[i-1], T.Union(root[i],read(),read());
else if(opt==2) root[i]=root[read()];
else root[i]=root[i-1], puts(T.fa[T.Get_fa(root[i],read())]==T.fa[T.Get_fa(root[i],read())]?"1":"0");
}
return 0;
}
BZOJ 3674：
//67820kb 724ms
//为啥我的空间开M*20就RE呢。。不管了反正也是跑到前10了。
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 600000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=2e5+5,M=2e5+5;
int n,root[M];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Segment_Tree
{
#define S M*21
#define lson son[x][0]
#define rson son[x][1]
int tot,fa[S],dep[S],son[S][2];
void Build(int &x,int l,int r)
{
x=++tot;
if(l==r) fa[x]=l;
else Build(lson,l,l+r>>1),Build(rson,(l+r>>1)+1,r);
}
void Add(int x,int l,int r,int p)//合并两个dep相同的集合时，使没被合并的那个dep+1
{
if(l==r) return (void)++dep[x];
int m=l+r>>1;
p<=m?Add(lson,l,m,p):Add(rson,m+1,r,p);
}
void Modify(int &x,int y,int l,int r,int pos,int v)//重建一遍 将pos处的fa改为v
{
x=++tot;
if(l==r) {fa[x]=v, dep[x]=dep[y]; return;}
int m=l+r>>1;
if(pos<=m) rson=son[y][1], Modify(lson,son[y][0],l,m,pos,v);
else lson=son[y][0], Modify(rson,son[y][1],m+1,r,pos,v);
}
int Query(int x,int l,int r,int pos)
{
if(l==r) return x;//返回树上一个节点(dep是节点的)
int m=l+r>>1;
return pos<=m?Query(lson,l,m,pos):Query(rson,m+1,r,pos);
}
int Get_fa(int rt,int x)
{
int p=Query(rt,1,n,x);//找到fa[p]==x的树上节点p(x是位置...)
return x==fa[p]?p:Get_fa(rt,fa[p]);
}
void Union(int &rt,int x,int y)
{
int p1=Get_fa(rt,x),p2=Get_fa(rt,y);
if(fa[p1]==fa[p2]) return;
if(dep[p1]>dep[p2]) std::swap(p1,p2);//r1->r2
Modify(rt,rt,1,n,fa[p1],fa[p2]);//fa[r1]=r2 -> fa[fa[p1]]=fa[p2]
if(dep[p1]==dep[p2]) Add(rt,1,n,fa[p2]);
}
}T;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
n=read(), T.Build(root[0],1,n);
for(int m=read(),i=1,opt,ans=0; i<=m; ++i)
{
if((opt=read())==1) root[i]=root[i-1], T.Union(root[i],read()^ans,read()^ans);
else if(opt==2) root[i]=root[read()^ans];
else root[i]=root[i-1], printf("%d\n",ans=(T.fa[T.Get_fa(root[i],read()^ans)]==T.fa[T.Get_fa(root[i],read()^ans)]));
}
return 0;
}
启发式合并：
//6492kb 56ms
#include <cstdio>
#include <cctype>
#include <algorithm>
//#define gc() getchar()
#define MAXIN 600000
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int N=2e4+5,M=2e4+5;
int n,root[M];
char IN[MAXIN],*SS=IN,*TT=IN;
struct Segment_Tree
{
#define S M*16
#define lson son[x][0]
#define rson son[x][1]
int tot,fa[S],sz[S],son[S][2];
void Build(int &x,int l,int r)
{
x=++tot;
if(l==r) fa[x]=l, sz[x]=1;
else Build(lson,l,l+r>>1),Build(rson,(l+r>>1)+1,r);
}
void Modify(int &x,int y,int l,int r,int pos,int v)//重建一遍 将pos处的fa改为v
{
x=++tot;
if(l==r) {fa[x]=v, sz[x]=sz[y]; return;}
int m=l+r>>1;
if(pos<=m) rson=son[y][1], Modify(lson,son[y][0],l,m,pos,v);
else lson=son[y][0], Modify(rson,son[y][1],m+1,r,pos,v);
}
int Query(int x,int l,int r,int pos)
{
if(l==r) return x;//返回树上一个节点(dep是节点的)
int m=l+r>>1;
return pos<=m?Query(lson,l,m,pos):Query(rson,m+1,r,pos);
}
int Get_fa(int rt,int x)
{
int p=Query(rt,1,n,x);//找到fa[p]==x的树上节点p(x是位置...)
return x==fa[p]?p:Get_fa(rt,fa[p]);
}
void Union(int &rt,int x,int y)
{
int p1=Get_fa(rt,x),p2=Get_fa(rt,y);
if(fa[p1]==fa[p2]) return;
if(sz[p1]>sz[p2]) std::swap(p1,p2);//r1->r2
sz[p2]+=sz[p1];
Modify(rt,rt,1,n,fa[p1],fa[p2]);//fa[r1]=r2 -> fa[fa[p1]]=fa[p2]
}
}T;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
n=read(), T.Build(root[0],1,n);
for(int m=read(),i=1,opt; i<=m; ++i)
{
if((opt=read())==1) root[i]=root[i-1], T.Union(root[i],read(),read());
else if(opt==2) root[i]=root[read()];
else root[i]=root[i-1], puts(T.fa[T.Get_fa(root[i],read())]==T.fa[T.Get_fa(root[i],read())]?"1":"0");
}
return 0;
}
