Peter_Matthew的博客

动态树

2019-01-04

本文共552字,大约需要阅读3分钟。

动态树的一些操作:
据说树剖能做的动态树都能做,但目前使(wo)用(zhi)最(xue)多(hui)的LCT不擅长处理子树操作(也有可能是我太菜了)

  • 单点修改/询问
  • 路径询问
  • 连边/删边
  • ······

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<bits/stdc++.h>
using namespace std;
int n,m,key[300005];
int top,ch[300005][2],fa[300005],xsm[300005],que[300005],rev[300005];
void pushup(int x){xsm[x]=xsm[ch[x][0]]^xsm[ch[x][1]]^key[x];}
void pushdown(int x)
{
if(rev[x])
{
rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;rev[x]^=1;
swap(ch[x][0],ch[x][1]);
}
}
bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rotate(int x)
{
int y=fa[x],z=fa[y],l=(ch[y][1]==x),r=l^1;
if(!isroot(y))
{
if(ch[z][0]==y)
ch[z][0]=x;
else
ch[z][1]=x;
}
fa[x]=z;
fa[y]=x;
fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];
ch[x][r]=y;
pushup(y);
pushup(x);
}
void splay(int x)
{
top=0;
que[++top]=x;
for(int i=x;!isroot(i);i=fa[i])
que[++top]=fa[i];
for(int i=top;i;i--)
pushdown(que[i]);
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))
{
if((ch[y][0]==x)^(ch[z][0]==y))rotate(x);
else rotate(y);
}
rotate(x);
}
}
void access(int x)
{
for(int t=0;x;t=x,x=fa[x])
{
splay(x);
ch[x][1]=t;
pushup(x);
}
}
void makeroot(int x)
{
access(x);
splay(x);
rev[x]^=1;
}
int find(int x)
{
access(x);
splay(x);
while(ch[x][0])
x=ch[x][0];
return x;
}
void split(int x,int y)
{
makeroot(x);
access(y);
splay(y);
}
void cut(int x,int y)
{
split(x,y);
if(ch[y][0]==x&&ch[x][1]==0)
ch[y][0]=fa[x]=0;
}
void link(int x,int y)
{
makeroot(x);
fa[x]=y;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&key[i]),xsm[i]=key[i];
for(int i=1,opt,x,y;i<=m;i++)
{
scanf("%d%d%d",&opt,&x,&y);
if(opt==0)split(x,y),printf("%d\n",xsm[y]);
if(opt==1)if(find(x)!=find(y))link(x,y);
if(opt==2)if(find(x)==find(y))cut(x,y);
if(opt==3)access(x),splay(x),key[x]=y,pushup(x);
}
return 0;
}

知识共享许可协议

知识共享许可协议

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏