CCZ在2015年8月25日也就是初三暑假要結束的時候就已經能切這種題了%%%

　　學習了另一種啟發式合并的方法，按秩合并，也就是按樹的深度合并，實際上是和按樹的大小一個道理，但是感覺（至少在這題上）更好處理一些。

　　然后就用可持久化線段樹來維護這個可持久化數組，就能做到可持久化并查集，可持久化平衡樹，可持久化之類的云云

　　3673不需要按秩合并，3674需要。。。用3674就能過倆，雙倍經驗雙倍的幸福！

#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> #include<cmath> #include<map> #define ll long long using namespace std; const int maxn=200010,inf=1e9; struct poi{int lt,rt,fa,dep;}tree[maxn*40]; int n,m,ty,x,y,z,tot,sz; int root[maxn]; void read(int &k) {int f=1;k=0;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();k*=f; } void build(int &x,int l,int r) {x=++sz;if(l==r){tree[x].fa=l;return;}int mid=(l+r)>>1;build(tree[x].lt,l,mid);build(tree[x].rt,mid+1,r); } void update(int &x,int l,int r,int cx,int delta) {tree[++sz]=tree[x];x=sz;if(l==r){tree[x].fa=delta;return;}int mid=(l+r)>>1;if(cx<=mid)update(tree[x].lt,l,mid,cx,delta);else update(tree[x].rt,mid+1,r,cx,delta); } void add(int &x,int l,int r,int cx) {tree[++sz]=tree[x];x=sz;if(l==r){tree[x].dep++;return;}int mid=(l+r)>>1;if(cx<=mid)add(tree[x].lt,l,mid,cx);else add(tree[x].rt,mid+1,r,cx); } int query(int x,int l,int r,int cx) {if(l==r)return x;int mid=(l+r)>>1;if(cx<=mid)return query(tree[x].lt,l,mid,cx);else return query(tree[x].rt,mid+1,r,cx); } int gf(int k,int x){int xx=query(k,1,n,x);return tree[xx].fa==x?xx:gf(k,tree[xx].fa);} int main() {read(n);read(m);build(root[0],1,n);for(int i=1;i<=m;i++){read(ty);root[i]=root[i-1];if(ty==1){read(x);read(y);x=gf(root[i],x);y=gf(root[i],y);if(tree[x].fa==tree[y].fa)continue;if(tree[x].dep>tree[y].dep)swap(x,y);update(root[i],1,n,tree[x].fa,tree[y].fa);if(tree[x].dep==tree[y].dep)add(root[i],1,n,tree[y].fa);}else if(ty==2)read(x),root[i]=root[x];else read(x),read(y),printf("%d\n",tree[gf(root[i],x)].fa==tree[gf(root[i],y)].fa);}return 0; } View Code

轉載于:https://www.cnblogs.com/Sakits/p/7418281.html

總結

以上是生活随笔為你收集整理的bzoj 36733674 可持久化并查集加强版（可持久化线段树+启发式合并）的全部內容，希望文章能夠幫你解決所遇到的問題。

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