前言
好了,晚自习要回来机房了。既然回都回了,那就好好复习把。
正文
作用
首先要搞清楚LCT可以干什么。简单来说,LCT可以维护一颗树上的链的信息,比如最大值,最小值,和与积等等(满足结合律的应该都可以)。、
然后,它还可以进行删边,加边和更改节点信息等操作。
这就是机草了
操作
首先是初始状态。初始状态就是每一个节点都是一条实链,然后每条树边都是一条虚链。
access(x)
这个操作是把根节点和x节点放在同一个splay当中:
inline void access(int x){
for(int y=0;x;y=x,x=f[x])
splay(x),c[x][1]=y,pushup(x);//儿子变了,需要及时上传信息
}
splay(x)
这个操作就是把节点x转到x所在的splay的根的位置上:
void rotate(int x)
{
int y=fa[x];
int z=fa[y];
int k=ch[y][1]==x;
int w=ch[x][1-k];
if (noroot(y))
{
ch[z][ch[z][1]==y]=x;
}
ch[x][1-k]=y;//Warning !!;
ch[y][k]=w;
if (w) fa[w]=y;
fa[x]=z;
fa[y]=x;
//pushup(x);
pushup(y);
}
void splay(int x)
{
int y=x;
int z=0;
st[++z]=y;
while (noroot(y))
{
st[++z]=fa[y];
// cout<<y<<" "<<fa[y]<<endl;
y=fa[y];
}
while (z) pushdown(st[z--]);
while (noroot(x))//转的是X,不是Y!!!
{
y=fa[x];
z=fa[y];
if (noroot(y))
{
rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
}
rotate(x);
}
pushup(x);
//pushup(y);
}
//splay和rotate就放在一起了。
makeroot(x)
这个函数可以将节点x变成LCT的根。
inline void pushr(int x){//Splay区间翻转操作
swap(c[x][0],c[x][1]);
r[x]^=1;//r为区间翻转懒标记数组
}
inline void makeroot(int x){
access(x);splay(x);
pushr(x);
}
Q:为什么pushr可以将splay整个反过来?
A:
每一个Splay维护的是一条从上到下按在原树中深度严格递增的路径,且中序遍历Splay得到的每个点的深度序列严格递增。
return;
其实理解了上面这一些东西就差不多全部懂了,剩下的来看这篇把:
LCT总结——概念篇+洛谷P3690 Link Cut Tree(动态树)(LCT,Splay)
终
发表回复