Stephen Horizon
Stephen Horizon

『OI笔记』LCT(再次?)

前言

  好了,晚自习要回来机房了。既然回都回了,那就好好复习把。

正文

作用

  首先要搞清楚LCT可以干什么。简单来说,LCT可以维护一颗树上的链的信息,比如最大值,最小值,和与积等等(满足结合律的应该都可以)。、
  然后,它还可以进行删边,加边和更改节点信息等操作。
  这就是机草了 :smile:

操作

  首先是初始状态。初始状态就是每一个节点都是一条实链,然后每条树边都是一条虚链。

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)

:smile:

Stephen Zeng

文章作者

发表评论

textsms
account_circle
email

Stephen Horizon

『OI笔记』LCT(再次?)
前言   好了,晚自习要回来机房了。既然回都回了,那就好好复习把。 正文 作用   首先要搞清楚LCT可以干什么。简单来说,LCT可以维护一颗树上的链的信息,比如最大值,最小值,和与积…
扫描二维码继续阅读
2021-09-07