LCT学习笔记

好菜啊，一直没学LCT。。。
1.怎么利用LCT中splay上的f[]数组得到原树中的点对应的父亲。
splay(x)，然后由于它的父亲深度比它浅，显然就是它的左儿子。
2.为什么link的时候要makeroot(x)而不是splay(x)即可。
因为只有makeroot(x)才能保证x的深度<y，这是才能心安理得地让f[y]=x。
3.注意LCT中的f[]这个数组，它不仅仅代表的是splay中的点的父亲，在x为某一棵splay的根节点时，f[x]代表了它的path_parent。
4.access(x)操作并不会使得x变成splay中的根，还需要补上一发splay操作。

#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#define N 440000
#define L 400000
#define eps 1e-7
#define inf 1e9+7
#define db double
#define ll long long
#define ldb long double
using namespace std;
inline int read()
{
    char ch=0;
    int x=0,flag=1;
    while(!isdigit(ch)){ch=getchar();if(ch==‘-‘)flag=-1;}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-‘0‘;ch=getchar();}
    return x*flag;
}
int v[N],f[N],st[N],sumv[N],flag[N],son[N][2];
bool isroot(int x){return (son[f[x]][0]!=x)&&(son[f[x]][1]!=x);}
void update(int x){flag[x]^=1;swap(son[x][0],son[x][1]);}
void pushup(int x){sumv[x]=sumv[son[x][0]]^sumv[son[x][1]]^v[x];}
void pushdown(int x)
{
    if(!flag[x])return;
    if(son[x][0])update(son[x][0]);
    if(son[x][1])update(son[x][1]);
    flag[x]=0;
}
bool getson(int x){return son[f[x]][1]==x;}
void rotate(int x)
{
    int y=f[x],z=f[y],tx=getson(x),ty=getson(y),p=son[x][!tx];
    if(!isroot(y))son[z][ty]=x;son[x][!tx]=y;son[y][tx]=p;
    if(p)f[p]=y;f[x]=z;f[y]=x;pushup(y);pushup(x);
}
void splay(int x)
{
    int cnt=0,tmp=x;
    st[++cnt]=x;
    while(!isroot(x))st[++cnt]=f[x],x=f[x];
    for(int i=cnt;i>=1;i--)pushdown(st[i]);
    x=tmp;
    while(!isroot(x))
    {
        int y=f[x];
        if(!isroot(y))rotate(getson(x)==getson(y)?x:y);
        rotate(x);
    }
    pushup(x);
}
void access(int x){for(int y=0;x;y=x,x=f[x])splay(x),son[x][1]=y,pushup(x);}
void makeroot(int x){access(x),splay(x);update(x);}
int findroot(int x)
{
    access(x);splay(x);
    while(son[x][0])pushdown(x),x=son[x][0];
    splay(x);return x;
}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);if(findroot(y)!=x)f[x]=y;}
void cut(int x,int y)
{
    makeroot(x);
    if(findroot(y)!=x||f[y]!=x||son[y][0])return;
    f[y]=son[x][1]=0;pushup(x);
}
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)v[i]=read();
    for(int i=1;i<=m;i++)
    {
        int flag=read()+1,x=read(),y=read();
        if(flag==1)split(x,y),printf("%d\n",sumv[y]);
        if(flag==2)link(x,y);
        if(flag==3)cut(x,y);
        if(flag==4)splay(x),v[x]=y,pushup(x);
    }
    return 0;
}

LCT学习笔记

原文：https://www.cnblogs.com/Creed-qwq/p/10352775.html