这世上只有两种人,会写LCT和不会写LCT的。
——蔻·德海克

LCT

第一次写动态树的数据结构,感受颇深。动态树,顾名思义,支持修改删点和加点的树,LCT可以维护一个这样的树,并支持较高效率地维护树链的信息。

功能

  • 维护并查询链上信息;
  • 动态加边或删边,修改权值;

结构

LCT可以维护一个或多个树。这些树(森林)被剖分成多个独立的链来维护,每一条链都通过灵活的splay链接组合起来。
一个结点存在且只存在于一个splay中,并且同一个splay中的每一个结点的深度都连续且不同。splay的中序遍历即为该链从上到下的dfs序。
就像这样
我们将在splay的根上维护链与链之间的信息:通过虚边相连。每一个虚边的儿子都保存父亲的信息,而虚边的父亲不会保存儿子,它还有更重要的splay的左右儿子要保存。

int val[N],son[N][2],fa[N],rev[N];

操作

splay操作

会LCT要先学会splay,会splay却不一定会写LCT,所以世界上就有了两种人,会写splay和不会写splay的人。

bool dir(int x){
    return son[fa[x]][1]==x;
}
bool nroot(int x){
    if(!x)return false;
    return son[fa[x]][dir(x)]==x;
}
void rever(int x){
    swap(son[x][1],son[x][0]);
    rev[x]^=1;
}
void upd(int x){
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
void psd(int x){
    if(rev[x]){
        rev[x]=false;
        rever(son[x][0]);
        rever(son[x][1]);
    }
}
void rotate(int x){
    int g=fa[fa[x]],f=fa[x],s=son[x][dir(x)^1],d=dir(x);
    if(nroot(fa[x]))son[g][dir(fa[x])]=x;
    fa[x]=g;
    son[x][d^1]=f;
    fa[f]=x;
    son[f][d]=s;
    if(s)fa[s]=f;
    upd(f),upd(x);
}
int sta[N],tot=0;
void splay(int x){
    for(int i=x;true;i=fa[i]){
        sta[tot++]=i;
        if(!nroot(i))break;
    }
    while(tot)psd(sta[--tot]);
    while(nroot(x)){
        if(nroot(fa[x])&&dir(fa[x])==dir(x))
            rotate(fa[x]);
        rotate(x);
    }
}

splay的一些经典操作了。但是要注意到,在LCT中有一个函数nroot,是用来判断一个结点是splay的根。在rotate和splay的操作中,一定要判断是不是根。

access操作

既然是动态树,就要有动态样。树链剖分维护的链是死的,但LCT维护的链是活的,我们将用access操作实现对树的一系列动态操作。
access的意思是接近,访问。在LCT上,access(x)代表了我们把根结点到结点x的路径单独割裂,形成同一个splay维护的链。
就像这样
之后的操作和信息维护就可以非常方便地在一棵splay上维护啦。
access要做的,是每次将所求的splay根与上层链相连。细节问题是,我们不知道现在splay的根是谁,以及上层链中我们想要舍去的不必要的部分,那些深度与现在splay中结点相同的一段链。
其实非常简单。我们splay(x)后,x就变成了当前splay的根节点,fa[x]就维护着上层链和本链相接的点。fa[x]的右儿子现在正维护着原本的那条重链,而将它赋成x,就意味着我们把fa[x]的重儿子改成了x。//原本的重儿子变成了轻儿子,区别只是son[fa[x]][1]里维护的是谁。
如此迭代反复,到根为止,就完成了通往神坛的第一步: access .

void access(int x){
    for(int y=0;x;y=x,x=fa[x]){
        splay(x);
        son[x][1]=y;
        upd(x);
    }
}

makeroot操作

我们能够轻而易举地将从根到点的路径剖出来了,但是问题还没有解决:如果我们想要维护两个非根结点之间的路径呢?换根操作此刻就意义重大了。
我们如果反转整个splay,那么原来最左边的点会变到最右边,在LCT的意义上,深度最浅的点变成了深度最深的点,反之亦然。而我们维护在这些节点上的关于树的形态信息,不会随之改变。所以我们可以access想要换为根的点,再将形成的splay整体反转,操作点的深度就变为整棵LCT中最浅的,也就意味着它变成了根。

void rever(int x){
    swap(son[x][1],son[x][0]);
    rev[x]^=1;
}
void maker(int x){
    access(x);splay(x);rever(x);
}

split操作

紧接着,提出两点间的路径这一操作就显得十分轻而易举了:先换根,再访问(access)。为了将信息统计到一个点上,我们顺手splay其中一个结点,作为链信息的统计点。

void split(int x,int y){
    maker(x);access(y);splay(y);
}

findroot操作

有时候我们需要知道两个点是否连通,可以通过比较两个所属LCT中的根节点是否相同判断。
findroot操作分为三步:access该结点, splay该结点, 访问该splay的最左儿子返回。因为在splay中根节点的深度最小,所以最左边的结点即为根节点。

int findr(int x){
    access(x),splay(x);
    while(son[x][0])x=son[x][0];
    splay(x);
    return x;
}

link/cut操作

link支持将两个原本不连通的LCT之间连边,cut支持将一个原本连通的两个点之间的边断开。
为了方便操作,link时只连一条虚边,更新其中一个点的fa即可;cut操作则是将他们split出来,输入合法的情况下,这两点之间必定直接连边,同时将son和fa赋值为零即可。

void link(int x,int y){
    maker(y);fa[y]=x;
}
void cut(int x,int y){
    split(x,y);
    son[y][0]=fa[x]=0;
    upd(y);
}

假使输入数据不保证合法性,则需要在操作前判断两个点的连通性,若不合法则跳过操作。

void link(int x,int y){
    maker(x);if(findr(y)^x)fa[x]=y;
}
inline void cut(int x,int y){
    split(x,y);
    if(!son[x][1]&&son[y][0]==x)
        fa[x]=son[y][0]=0;
    upd(y);
}

完整的板子

#include<bits/stdc++.h>
#define N 100010
using namespace std;
int val[N],sum[N],son[N][2],fa[N],rev[N];
void upd(int x){
    sum[x]=sum[son[x][0]]^sum[son[x][1]]^val[x];
}
void rever(int x){
    rev[x]^=1,swap(son[x][0],son[x][1]);
}
void psd(int x){
    if(rev[x]){
        rev[x]=false;
        rever(son[x][0]);
        rever(son[x][1]);
    }
}
bool dir(int x){
    return son[fa[x]][1]==x;
}
bool root(int x){
    if(x==0)return true;
    return son[fa[x]][dir(x)]!=x;
}
void rotate(int x){
    int g=fa[fa[x]],f=fa[x],d=dir(x),s=son[x][d^1];
    if(!root(f))son[g][dir(fa[x])]=x;
    fa[x]=g;
    fa[f]=x;
    son[x][d^1]=f;
    son[f][d]=s;
    if(s)fa[s]=f;
    upd(f),upd(x);//注意先后
}
int sta[N],tot=0;
void splay(int x){
    for(int t=x;1;t=fa[t]){
        sta[tot++]=t;
        if(root(t))break;
    }
    while(tot)psd(sta[--tot]);
    while(!root(x)){
        if(fa[x]&&(!root(fa[x]))&&dir(fa[x])==dir(x))
            rotate(fa[x]);
        rotate(x);
    }
}
void access(int x){
    for(int tmp=0;x;tmp=x,x=fa[x]){
        splay(x);
        son[x][1]=tmp;
        upd(x);
    }
}
void maker(int x){
    access(x),splay(x),rever(x);
}
int findr(int x){
    access(x),splay(x);
    while(son[x][0])x=son[x][0];
    splay(x);
    return x;
}
void split(int x,int y){
    maker(x),access(y),splay(y);
}
void link(int x,int y){
    maker(x);if(findr(y)^x)fa[x]=y;
}
inline void cut(int x,int y){
    split(x,y);
    if(!son[x][1]&&son[y][0]==x)
        fa[x]=son[y][0]=0;
    upd(y);
}
int n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&val[i]);
    while(m--){
        int opt,x,y;scanf("%d%d%d",&opt,&x,&y);
        if(opt==0){
            split(x,y);
            printf("%d\n",sum[y]);
        }
        if(opt==1){
            link(x,y);
        }
        if(opt==2){
            cut(x,y);
        }
        if(opt==3){
            splay(x);
            val[x]=y;
            upd(x);
        }
    }
}

题目大意

可修改的n个弹力值v_i,表示第i个点能将绵羊弹到v_i个格子之后的点。每次询问该点的绵羊将在多少次弹射之后飞出序列。
n \leq 200000

题解

将一个点和它能弹到的点link,能弹飞的点与第n+1个点link。
对于询问,输出split(x,n+1)之后链的siz。
注意下标从零开始,应该加一。

#include<cstdio>
#include<algorithm>
#define N 200010
using namespace std;
int siz[N],son[N][2],fa[N],rev[N];
bool dir(int x){
    return son[fa[x]][1]==x;
}
bool nroot(int x){
    if(!x)return false;
    return son[fa[x]][dir(x)]==x;
}
void rever(int x){
    swap(son[x][1],son[x][0]);
    rev[x]^=1;
}
void upd(int x){
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
void psd(int x){
    if(rev[x]){
        rev[x]=false;
        rever(son[x][0]);
        rever(son[x][1]);
    }
}
void rotate(int x){
    int g=fa[fa[x]],f=fa[x],s=son[x][dir(x)^1],d=dir(x);
    if(nroot(fa[x]))son[g][dir(fa[x])]=x;
    fa[x]=g;
    son[x][d^1]=f;
    fa[f]=x;
    son[f][d]=s;
    if(s)fa[s]=f;
    upd(f),upd(x);
}
int sta[N],tot=0;
void splay(int x){
    for(int i=x;true;i=fa[i]){
        sta[tot++]=i;
        if(!nroot(i))break;
    }
    while(tot)psd(sta[--tot]);
    while(nroot(x)){
        if(nroot(fa[x])&&dir(fa[x])==dir(x))
            rotate(fa[x]);
        rotate(x);
    }
}
void access(int x){
    for(int y=0;x;y=x,x=fa[x]){
        splay(x);
        son[x][1]=y;
        upd(x);
    }
}
int findr(int x){
    access(x);splay(x);
    while(son[x][0])x=son[x][0];
    splay(x);
    return x;
}
void maker(int x){
    access(x);splay(x);rever(x);
}
void split(int x,int y){
    maker(x);access(y);splay(y);
}
void link(int x,int y){
    maker(y);fa[y]=x;
}
void cut(int x,int y){
    split(x,y);
    son[y][0]=fa[x]=0;
    upd(y);
}
int n,m,v[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&v[i]);
        if(i+v[i]<=n)link(i,i+v[i]);
        else link(i,n+1);
    }
    scanf("%d",&m);
    while(m--){
        int opt,x,k;
        scanf("%d%d",&opt,&x);x++;
        if(opt==1){
            split(x,n+1);
            printf("%d\n",siz[n+1]-1);
        }
        if(opt==2){
            cut(x,x+v[x]>n?n+1:x+v[x]);
            scanf("%d",&v[x]);
            link(x,x+v[x]>n?n+1:x+v[x]);
        }
    }
}

血まみれからの方がさ,勝つ時にはカッコイイだろう.