蒟蒻比較菜，現在才學。。。

P3402 可持久化并查集

其實就是魔改的主席樹啦，記錄每個點的直接父親與這棵子樹的大小。

合并的時候不用路徑壓縮，直接暴力跳父親，\(O(\log^2)\) 找到祖先，之后啟發式合并(啟發式合并的平均復雜度達到 \(O(\log n)\))。

需要注意的是可能會先繼承刪一個版本，并有兩次在同一個版本上的修改。這是我們需要先復制版本，再在這個版本上動態開點修改父親。

$\texttt{code}$ // Author:A weak man named EricQian #include<bits/stdc++.h> using namespace std; #define infll 0x7f7f7f7f7f7f7f7f #define inf 0x3f3f3f3f #define Maxn 200005 typedef long long ll; inline int rd() {int x=0;char ch,t=0;while(!isdigit(ch = getchar())) t|=ch=='-';while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();return x=t?-x:x; } inline ll maxll(ll x,ll y){ return x>y?x:y; } inline ll minll(ll x,ll y){ return x<y?x:y; } inline ll absll(ll x){ return x>0ll?x:-x; } inline ll gcd(ll x,ll y){ return (y==0)?x:gcd(y,x%y); } int n,m,tot; int root[Maxn]; struct TREE { int ls,rs,fa,siz; }tree[Maxn<<5]; void build(int &p,int nl,int nr) {if(!p) p=++tot;if(nl==nr){ tree[p].fa=nl,tree[p].siz=1; return; }int mid=(nl+nr)>>1;build(tree[p].ls,nl,mid),build(tree[p].rs,mid+1,nr); } TREE query(int p,int nl,int nr,int x) {if(nl==nr) return tree[p];int mid=(nl+nr)>>1;if(mid>=x) return query(tree[p].ls,nl,mid,x);else return query(tree[p].rs,mid+1,nr,x); } TREE Find(int p,int x) {TREE tmp=query(p,1,n,x);if(tmp.fa==x) return tmp;return Find(p,tmp.fa); } void change(int p,int nl,int nr,int x,int F,int S) {if(nl==nr) { tree[p].fa=F,tree[p].siz=S; return; }int mid=(nl+nr)>>1;if(mid>=x){tree[++tot]=tree[tree[p].ls],tree[p].ls=tot;change(tree[p].ls,nl,mid,x,F,S);}else{tree[++tot]=tree[tree[p].rs],tree[p].rs=tot;change(tree[p].rs,mid+1,nr,x,F,S);} } int main() {//ios::sync_with_stdio(false); cin.tie(0);//freopen(".in","r",stdin);//freopen(".out","w",stdout);n=rd(),m=rd(),build(root[0],1,n);TREE sa,sb;for(int i=1,opt,a,b,k;i<=m;i++){opt=rd();if(opt==1){root[i]=++tot,tree[root[i]]=tree[root[i-1]];a=rd(),b=rd(),sa=Find(root[i],a),sb=Find(root[i],b); // if(sa.fa==sb.fa) continue;if(sa.siz>sb.siz)change(root[i],1,n,sb.fa,sa.fa,sb.siz),change(root[i],1,n,sa.fa,sa.fa,sa.siz+sb.siz);elsechange(root[i],1,n,sa.fa,sb.fa,sa.siz),change(root[i],1,n,sb.fa,sb.fa,sa.siz+sb.siz);}else if(opt==2) k=rd(),root[i]=root[k];else{a=rd(),b=rd(),root[i]=root[i-1];sa=Find(root[i],a),sb=Find(root[i],b);if(sa.fa==sb.fa) printf("1\n");else printf("0\n");}}//fclose(stdin);//fclose(stdout);return 0; }

總結

以上是生活随笔為你收集整理的可持久化并查集的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。