【OI之路】02数据结构-7动态树

LCT

文章

师兄写的
浅谈LCT实现及应用.pdf

板子

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
struct LCT
{
struct Nod{int son[2],fa;bool fz;}p[MAX_N];
LCT(){memset(p,0,sizeof p);}
bool son(int x) {return p[p[x].fa].son[1]==x;}
void pushdown(int x)
{
if(!p[x].fz) return;
p[x].fz=0;
int lc=p[x].son[0];p[lc].fz^=1;swap(p[lc].son[0],p[lc].son[1]);
int rc=p[x].son[1];p[rc].fz^=1;swap(p[rc].son[0],p[rc].son[1]);
}
void rotate(int x)
{
int f=p[x].fa,ff=p[f].fa;if(p[ff].son[son(f)]==f) p[ff].son[son(f)]=x;
int w=son(x),t=p[x].son[w^1];p[f].son[w]=t;p[x].son[w^1]=f;
p[x].fa=ff;p[f].fa=x;p[t].fa=f;
}
bool isroot(int x) {return p[x].fa==0 or (p[p[x].fa].son[0]!=x and p[p[x].fa].son[1]!=x);}
int tmp[MAX_N];
void splay(int x)
{
int tot=0,now=x;while(!isroot(now)) tmp[++tot]=now,now=p[now].fa;
tmp[++tot]=now;for(int i=tot;i>=1;i--) pushdown(tmp[i]);
for(int f=p[x].fa;!isroot(x);rotate(x),f=p[x].fa)
if(!isroot(f)) son(x)^son(f)?rotate(x):rotate(f);
}
void access(int x)
{
int lst=0;
while(x!=0)
{
splay(x);
p[x].son[1]=lst;p[lst].fa=x;
lst=x;x=p[x].fa;
}
}
void makeroot(int x)
{
access(x);splay(x);
p[x].fz^=1;swap(p[x].son[0],p[x].son[1]);
}
void link(int x,int y)
{
makeroot(y);
p[y].fa=x;
}
void cut(int x,int y)
{
makeroot(x);access(y);splay(y);
p[y].son[0]=0;p[x].fa=0;
}
int getroot(int x)
{
access(x);splay(x);
while(p[x].son[0]) pushdown(x=p[x].son[0]);
splay(x);
return x;
}
}lct;

好题

CF#545F

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/e23c.html
转载请注明出处,谢谢!