lct代码讲解

· · 题解

(为自己的博客打个广告看看吧)

题目链接

因为lct有各种dalao讲解了，我这里就不做原理讲解。

代码有详细讲解，我这里直接在代码上注释了一下容易错和难想的地方（相信能帮到你们不多走弯路！）

Update:我当时做这题的时候貌似link不会出现已经联通，以前的代码在改了数据后就出了问题，不过现在已经修复，代码可以AC 2020.10.19的数据

另：对部分地方进行微调，使得代码写起来和看起来能更舒服

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,m;
struct node{
    int fa,ch[2],sum,val,lazy;
}t[310000];
#define lc t[x].ch[0]
#define rc t[x].ch[1]
//方便书写 
//lc表示x左儿子
//rc表示x右儿子 
inline bool root(int x){//判断是否是splay根节点,因为存在虚边,所以不能通过判断fa==0来判断 
    int g=t[x].fa;
    return t[g].ch[0]!=x&&t[g].ch[1]!=x;//若为根,则父亲节点不应该有这个儿子(父不认子)
}
inline void pushup(int x){
    t[x].sum=t[x].val^t[lc].sum^t[rc].sum;
}
inline void pushr(int x){//不解释 
    if(!x)return;
    swap(lc,rc);
    t[x].lazy^=1;
}
inline void pushdown(int x){
    if(t[x].lazy){
        pushr(lc);
        pushr(rc);
        t[x].lazy=0;
    }
}
inline void push(int x){//因为 正常splay操作下 ,都要先kth或者是直接在splay操作中加pushdown,而lct中则没有
    if(!root(x))push(t[x].fa);// 因此要从根到x全部pushdown 
    pushdown(x);
}
inline void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int k=t[y].ch[1]==x;
    if(!root(y)) t[z].ch[t[z].ch[1]==y]=x;//正常splay,根的fa为 0,因此不用判断,这里必须特判!! 
    t[x].fa=z;
    t[y].ch[k]=t[x].ch[k^1];
    if(t[x].ch[k^1])t[t[x].ch[k^1]].fa=y;
    t[y].fa=x;
    t[x].ch[k^1]=y;
    pushup(y);
}
inline void splay(int x){
    int y,z;
    push(x);//先pushdown,否则会破坏标记,splay中大部分先查找第k大再操作那时已经下放标记,lct绝对不存在 
    while(!root(x)){
        y=t[x].fa,z=t[y].fa;
        if(!root(y))
            (t[z].ch[0]==y)^(t[y].ch[0]==x)?rotate(x):rotate(y);
        rotate(x);
    }
    pushup(x);
}
inline void access(int x){//将x与根放在同一个splay树,此时根为splay最左边的节点,x为splay最右边的节点 
    for(int y=0;x;y=x,x=t[x].fa){
        splay(x);rc=y;pushup(x);//因为按照深度排序,将上面一个父节点的右儿子设为自己,那么之前的实边就变为
    }                                   //虚边了,即没有这个儿子了,但是fa标记还在,此时要pushup 
}
inline void makeroot(int x){//将x作为原树的根 
    access(x);splay(x);//access后,x肯定为splay树的最右边节点,因为下面和他连的边全变成了虚边 
    pushr(x);          //所以此时旋转到根后,排序顺序相反,所以要反转使其满足左边深度小,右边深度大 
}
inline void split(int x,int y){//将x,y这条路径变为一颗splay中的节点 
    makeroot(x);
    access(y);
    splay(y);//这句话一定要,因为access时,假如x,y和access到的z已经在一棵splay树,z为splay的根而不一定z就是y,然后z往上跳就是0
    //可以画个图看一下呢, y和z 一定是在一棵splay上的,再分z,x上否在一棵splay上讨论,会发现splay(y)(或splay(x))一定要 
}
inline void link(int x,int y){//将x,y这两个分别属于不同lct的点连边
    makeroot(x);//这句话一定要,因为是将x,y连边 ,而原来 x可能还有fa
    t[x].fa=y;
}
inline void cut(int x,int y){//将x,y的边切断 
    makeroot(x);
    access(y);
    splay(y);
    if(t[y].ch[0]!=x||rc)return;//如果x,y直接相连,即中间没有点,并且比y深度小的是x(makeroot了,强制dep(x)<dep(y)) 
    //y的左儿子不是x说明x与y不相连或者之间存在其他的点,x右儿子存在也说明xy之间存在其他的点
    //即x,y的边不存在 
    t[x].fa=t[y].ch[0]=0;
    pushup(x);
}inline int findroot(int x){
    access(x),splay(x);
    while(lc)pushdown(x),x=lc;
    pushdown(x);
    return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&t[i].val);
        t[i].sum=t[i].val;
    }
    int opt,a,b;
    while(m--){
        scanf("%d%d%d",&opt,&a,&b);
        switch(opt){
            case 0:{
                if(a==b){
                    printf("%d\n",t[a].val);
                    break;
                }
                split(a,b);
                pushup(b);
                printf("%d\n",t[b].sum);
                break;
            }
            case 1:{
                if(findroot(a)!=findroot(b))link(a,b);
                break;
            }
            case 2:{
                cut(a,b);
                break;
            }
            case 3:{
                splay(a);
                t[a].val=b;
                pushup(a);
                break;
            }
        }
    }
    return 0;
}