『OI笔记』LCT（再次？）

Last updated on June 18, 2024 pm

前言

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

正文

作用

首先要搞清楚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);
}