『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: