[关闭]
@zzzc18 2017-08-04T00:44:44.000000Z 字数 2680 阅读 415

模板

LCT


LCT中最主要的是操作,操作的含义是,从当前的节点u向他所在的根节点连一条重路径,这是相当于把沿路的重路径全都断开,重新拉一条从u到根的重路径。

操作:

若想让u成为当前树的根节点,则可以先,再,把u转为当前splay的根节点。因为splay维护的是深度,所以u没有右儿子(没有比u还要深的点,因为重链定义),所以换根就相当于一次区间翻转,交换左右子树即完成区间翻转。此时就可以打标记了。

所以,

还有一个操作,就是判断这是不是一条重路径的根,只要他的fa指针指向的节点的左右子树都不是他(证明此时这是一条虚边),那么这就是一棵子树的根节点。

操作:

在u和v之间连边,可以,再让的父亲为,这就相当于本身是一棵,而之间连了条轻边。

操作:

断开之间的边,可以先,再,再,此时的左儿子必定为,于是断开的左儿子即可。

至于翻转标记的传递,就是跟一样就行了。

但标记下放有一个问题。因为是时时刻刻在分裂与合并的,因为要动态维护每条重链,所以在之前,要先把根节点到当前节点全部下放一遍标记,防止标记下放不完全。

操作:

相当于把两个子树分开,考虑到我们的时候第一步也是分开,所以

然后还要保存一些轻边(虚边),对于轻边我们需要单独记录处理。在原树上,当前重链的顶端节点与他的父亲的边即为轻边,如果不记录,树将是不完整的。

具体到代码实现,可以是当前的根节点的父亲即为当前上面的那个重链所在的上的点,但上面的的儿子并不指向当前的父亲,即为用的根节点的父亲来存储轻边。

动态树的主要时间消耗在上,而的时间复杂度是

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. #define MAXN 300000+9
  5. using namespace std;
  6. int n,m;
  7. int val[MAXN],xr[MAXN];
  8. int son[MAXN][2];
  9. int fa[MAXN],rev[MAXN],xorsum[MAXN];
  10. bool isroot(int x){
  11. int y=fa[x];
  12. if(son[y][0]!=x && son[y][1]!=x)
  13. return true;
  14. return false;
  15. }
  16. void update(int x){
  17. xr[x]=val[x]^xr[son[x][0]]^xr[son[x][1]];
  18. }
  19. void pushdown(int x){
  20. int ls=son[x][0],rs=son[x][1];
  21. if(rev[x]){
  22. rev[ls]^=1;
  23. rev[rs]^=1;
  24. rev[x]^=1;
  25. swap(son[x][0],son[x][1]);
  26. }
  27. }
  28. void rotate(int x){
  29. int y=fa[x],z=fa[y];
  30. int tmp1,tmp2;
  31. tmp1= son[y][0]==x ? 0 : 1;
  32. tmp2=tmp1^1;
  33. if(!isroot(y)){
  34. if(son[z][0]==y)
  35. son[z][0]=x;
  36. else
  37. son[z][1]=x;
  38. }
  39. fa[x]=z;
  40. fa[y]=x;
  41. fa[son[x][tmp2]]=y;
  42. son[y][tmp1]=son[x][tmp2];
  43. son[x][tmp2]=y;
  44. update(y);
  45. update(x);
  46. }
  47. int sta[MAXN];
  48. void splay(int x){
  49. int top=1;
  50. sta[top]=x;
  51. int i;
  52. for(i=x; !isroot(i) ;i=fa[i]) sta[++top]=fa[i];
  53. while(top)
  54. pushdown(sta[top--]);
  55. while(!isroot(x)){
  56. int y=fa[x],z=fa[y];
  57. if(!isroot(y)){
  58. if((son[y][0]==x)^(son[z][0]==y))
  59. rotate(x);
  60. else
  61. rotate(y);
  62. }
  63. rotate(x);
  64. }
  65. }
  66. void access(int x){
  67. int i;
  68. for(i=0;x;i=x,x=fa[x]){
  69. splay(x);
  70. son[x][1]=i;
  71. update(x);
  72. }
  73. }
  74. void makeroot(int x){
  75. access(x);
  76. splay(x);
  77. rev[x]^=1;
  78. }
  79. void Link(int x,int y){
  80. makeroot(x);
  81. fa[x]=y;
  82. }
  83. void split(int x,int y){
  84. makeroot(x);
  85. access(y);
  86. splay(y);
  87. }
  88. void Cut(int x,int y){
  89. split(x,y);
  90. if(son[y][0]==x){
  91. son[y][0]=0;
  92. fa[x]=0;
  93. }
  94. }
  95. int FindFather(int x){
  96. access(x);
  97. splay(x);
  98. while(son[x][0])
  99. x=son[x][0];
  100. return x;
  101. }
  102. void solve(){
  103. int i;
  104. int opt,x,y;
  105. for(i=1;i<=m;i++){
  106. scanf("%d",&opt);
  107. if(opt==0){
  108. scanf("%d%d",&x,&y);
  109. split(x,y);
  110. printf("%d\n",xr[y]);
  111. }
  112. if(opt==1){
  113. scanf("%d%d",&x,&y);
  114. int xx=FindFather(x);
  115. int yy=FindFather(y);
  116. if(xx!=yy)
  117. Link(x,y);
  118. }
  119. if(opt==2){
  120. scanf("%d%d",&x,&y);
  121. int xx=FindFather(x);
  122. int yy=FindFather(y);
  123. if(xx==yy)
  124. Cut(x,y);
  125. }
  126. if(opt==3){
  127. scanf("%d%d",&x,&y);
  128. access(x);
  129. splay(x);
  130. val[x]=y;
  131. update(x);
  132. }
  133. }
  134. }
  135. int main(){
  136. scanf("%d%d",&n,&m);
  137. int i;
  138. for(i=1;i<=n;i++){
  139. scanf("%d",&val[i]);
  140. xr[i]=val[i];
  141. }
  142. solve();
  143. return 0;
  144. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注