洛谷P3402 可持久化并查集

n个集合 m个操作

操作：

1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0

说是可持久化并查集，实际上是把并查集的所有find和merge操作都放到可持久化数组上做，这样可以做到完全可持久化（不仅能查询某个历史版本，而且还能在某个历史版本的基础上进行修改）

注意并查集要按秩合并

可持久化数组可以用可持久化线段树(主席树)或者可持久化平衡树实现，理论上平衡树应该更快一些而且更省内存(但也省不了多少)

线段树版：

 #include<bits/stdc++.h>

 using namespace std;

 const int N=2e5+;

 int rt[N],fa[N*],mxd[N*],ls[N*],rs[N*],tot,n,m;

 #define mid ((l+r)>>1)

 int cpy(int v) {int u=++tot; fa[u]=fa[v],mxd[u]=mxd[v],ls[u]=ls[v],rs[u]=rs[v]; return u;}

 int qry(int* a,int p,int& u,int l=,int r=n) {

     if(l==r)return a[u];

     return p<=mid?qry(a,p,ls[u],l,mid):qry(a,p,rs[u],mid+,r);

 }

 void upd(int* a,int p,int x,int v,int& u,int l=,int r=n) {

     u=cpy(v);

     if(l==r) {a[u]=x; return;}

     p<=mid?upd(a,p,x,ls[v],ls[u],l,mid):upd(a,p,x,rs[v],rs[u],mid+,r);

 }

 int fd(int x,int u) {

     int fx=qry(fa,x,u);

     return fx?fd(fx,u):x;

 }

 void mg(int x,int y,int& u) {

     int fx=fd(x,u),fy=fd(y,u);

     if(fx==fy)return;

     int dx=qry(mxd,fx,u),dy=qry(mxd,fy,u);

     if(dx>dy)swap(fx,fy),swap(dx,dy);

     upd(fa,fx,fy,u,u);

     if(dx==dy)upd(mxd,fy,dx+,u,u);

 }

 int main() {

     mxd[]=;

     scanf("%d%d",&n,&m);

     for(int i=; i<=m; ++i) {

         rt[i]=rt[i-];

         int f,x,y;

         scanf("%d",&f);

         if(f==)scanf("%d%d",&x,&y),mg(x,y,rt[i]);

         else if(f==)scanf("%d",&x),rt[i]=rt[x];

         else scanf("%d%d",&x,&y),printf("%d\n",fd(x,rt[i])==fd(y,rt[i]));

     }

     return ;

 }

平衡树版：(由于没有旋转分裂等操作所以代码和线段树基本没区别，只是二分判断的条件稍微改了一下)

 #include<bits/stdc++.h>

 using namespace std;

 const int N=2e5+;

 int rt[N],fa[N*],mxd[N*],ls[N*],rs[N*],tot,n,m;

 #define mid ((l+r)>>1)

 int cpy(int v) {int u=++tot; fa[u]=fa[v],mxd[u]=mxd[v],ls[u]=ls[v],rs[u]=rs[v]; return u;}

 int qry(int* a,int p,int& u,int l=,int r=n) {

     if(p==mid)return a[u];

     return p<mid?qry(a,p,ls[u],l,mid-):qry(a,p,rs[u],mid+,r);

 }

 void upd(int* a,int p,int x,int v,int& u,int l=,int r=n) {

     u=cpy(v);

     if(p==mid) {a[u]=x; return;}

     p<mid?upd(a,p,x,ls[v],ls[u],l,mid-):upd(a,p,x,rs[v],rs[u],mid+,r);

 }

 int fd(int x,int u) {

     int fx=qry(fa,x,u);

     return fx?fd(fx,u):x;

 }

 void mg(int x,int y,int& u) {

     int fx=fd(x,u),fy=fd(y,u);

     if(fx==fy)return;

     int dx=qry(mxd,fx,u),dy=qry(mxd,fy,u);

     if(dx>dy)swap(fx,fy),swap(dx,dy);

     upd(fa,fx,fy,u,u);

     if(dx==dy)upd(mxd,fy,dx+,u,u);

 }

 int main() {

     mxd[]=;

     scanf("%d%d",&n,&m);

     for(int i=; i<=m; ++i) {

         rt[i]=rt[i-];

         int f,x,y;

         scanf("%d",&f);

         if(f==)scanf("%d%d",&x,&y),mg(x,y,rt[i]);

         else if(f==)scanf("%d",&x),rt[i]=rt[x];

         else scanf("%d%d",&x,&y),printf("%d\n",fd(x,rt[i])==fd(y,rt[i]));

     }

     return ;

 }

巴特西

洛谷P3402 可持久化并查集

最新文章

热门文章