BZOJ3674：可持久化并查集加强版

浅谈主席树：https://www.cnblogs.com/AKMer/p/9956734.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=3674

因为要支持历史操作，所以我们用可持久化线段树来维护并查集的祖先数组。

因为要路径压缩，所以每个点会被建\(k*logn\)次，\(k\)未知，但是绝对不大。

时间复杂度：\(O(mklogn)\)

空间复杂度：\(O(mklogn)\)

代码如下：

#include <cstdio>
using namespace std;const int maxn=2e5+5;int rt[maxn];
int n,m,lstans;int read() {
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';
return x*f;
}struct tree_node {
int fa,ls,rs;
};struct Chairman_tree {
int tot;
tree_node tree[maxn*40];void build(int &now,int l,int r) {
now=++tot;
if(l==r) {tree[now].fa=l;return;}
int mid=(l+r)>>1;
build(tree[now].ls,l,mid);
build(tree[now].rs,mid+1,r);
}int query(int now,int l,int r,int pos) {
if(l==r)return tree[now].fa;
int mid=(l+r)>>1;
if(pos<=mid)return query(tree[now].ls,l,mid,pos);
return query(tree[now].rs,mid+1,r,pos);
}void change(int lst,int &now,int l,int r,int pos,int v) {
now=++tot;tree[now]=tree[lst];
if(l==r) {tree[now].fa=v;return;}
int mid=(l+r)>>1;
if(pos<=mid)change(tree[lst].ls,tree[now].ls,l,mid,pos,v);
else change(tree[lst].rs,tree[now].rs,mid+1,r,pos,v);
}
}T;int find(int &root,int x) {
int f=T.query(root,1,n,x);
if(f==x)return x;
int res=find(root,f);
T.change(root,root,1,n,x,res);//路径压缩相当于在上一版本主席树上面更改祖先数组
return res;
}int main() {
n=read(),m=read();
T.build(rt[0],1,n);
for(int i=1;i<=m;i++) {
int opt=read();
if(opt==1) {
int a=read()^lstans,b=read()^lstans;
int p=find(rt[i-1],a),q=find(rt[i-1],b);
if(p==q)rt[i]=rt[i-1];//如果不需要合并就不合并
else T.change(rt[i-1],rt[i],1,n,p,q);
}
else if(opt==2) {
int t=read()^lstans;
rt[i]=rt[t];
}
else if(opt==3) {
int a=read()^lstans,b=read()^lstans;
int p=find(rt[i-1],a),q=find(rt[i-1],b);
if(p==q)lstans=1;
else lstans=0;
rt[i]=rt[i-1];//询问也算操作
printf("%d\n",lstans);
}
}
return 0;
}