[关闭]
@ysner 2018-08-17T22:12:04.000000Z 字数 1924 阅读 1942

可持久化并查集小结

并查集 数据结构


定义

允许恢复历史状态的并查集。

建立

棵主席树,每个主席树上维护当前状态并查集各个节点的父亲。
(实际上就是并查集和主席树强行捆绑在一起)

操作

每次操作前自动继承上次操作后的状态。

用途

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cmath>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define ll long long
  8. #define re register
  9. #define il inline
  10. #define ls t[x][0]
  11. #define rs t[x][1]
  12. #define max(a,b) ((a)>(b)?(a):(b))
  13. #define min(a,b) ((a)<(b)?(a):(b))
  14. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  15. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  16. using namespace std;
  17. const int N=5e6+100;
  18. int n,m,rt[N],tot,f[N],t[N][2],d[N];
  19. il int gi()
  20. {
  21. re int x=0,t=1;
  22. re char ch=getchar();
  23. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  24. if(ch=='-') t=-1,ch=getchar();
  25. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  26. return x*t;
  27. }
  28. il void Build(re int &x,re int l,re int r)
  29. {
  30. x=++tot;
  31. if(l==r) {f[x]=l;return;}
  32. re int mid=l+r>>1;
  33. Build(ls,l,mid);Build(rs,mid+1,r);
  34. }
  35. il void Modify(re int &x,re int las,re int l,re int r,re int pos,re int ff)
  36. {
  37. x=++tot;
  38. if(l==r) {f[x]=ff;d[x]=d[las];return;}
  39. re int mid=l+r>>1;
  40. ls=t[las][0];rs=t[las][1];
  41. if(pos<=mid) Modify(ls,t[las][0],l,mid,pos,ff);
  42. else Modify(rs,t[las][1],mid+1,r,pos,ff);
  43. }
  44. il int Query(re int x,re int l,re int r,re int pos)
  45. {
  46. if(l==r) return x;
  47. re int mid=l+r>>1;
  48. if(pos<=mid) return Query(ls,l,mid,pos);
  49. else return Query(rs,mid+1,r,pos);
  50. }
  51. il void add(re int x,re int l,re int r,re int pos)
  52. {
  53. if(l==r) {++d[x];return;}
  54. re int mid=l+r>>1;
  55. if(pos<=mid) add(ls,l,mid,pos);
  56. else add(rs,mid+1,r,pos);
  57. }
  58. il int find(re int rt,re int x)
  59. {
  60. re int fa=Query(rt,1,n,x);
  61. return x==f[fa]?fa:find(rt,f[fa]);
  62. }
  63. int main()
  64. {
  65. n=gi();m=gi();
  66. Build(rt[0],1,n);
  67. fp(i,1,m)
  68. {
  69. re int op=gi();
  70. if(op==1)
  71. {
  72. rt[i]=rt[i-1];
  73. re int x=find(rt[i],gi()),y=find(rt[i],gi());
  74. if(f[x]==f[y]) continue;
  75. if(d[x]>d[y]) swap(x,y);
  76. Modify(rt[i],rt[i-1],1,n,f[x],f[y]);
  77. if(d[x]==d[y]) add(rt[i],1,n,f[y]);
  78. }
  79. if(op==2) rt[i]=rt[gi()];
  80. if(op==3)
  81. {
  82. rt[i]=rt[i-1];
  83. re int x=find(rt[i],gi()),y=find(rt[i],gi());
  84. puts(f[x]==f[y]?"1":"0");
  85. }
  86. }
  87. return 0;
  88. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注