唔，其实我不会 Splay，但是我会 LCT。
众所周知，会 LCT 和会 Splay 是两回事，因为 LCT 只需要旋至根即可。
到现在还是不会，但是先把 LCT 的 Splay 写一下吧。
自己复习用的。
先给代码。
LCT code
int isroot(int x) {return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
int idt(int x) {return ch[fa[x]][1]==x;}
void swp(int x) {
if(!x) return ;
rev[x]^=1;
swap(ls,rs);
}
void pushdown(int x) {
if(rev[x]) {
rev[x]=0;
swp(ls);
swp(rs);
}
}
void pushup(int x) {
if(!x) return;
if(x<=n) ma[x]=-INF;
else ma[x]=val[x];
if(ls) cmax(ma[x],ma[ls]);
if(rs) cmax(ma[x],ma[rs]);
}
void pushall(int x) {
if(!isroot(x)) pushall(fa[x]);
pushdown(x);
}
void add(int y,int x,int i) {ch[fa[x]=y][i]=x;}
void rotate(int x) {
int y=fa[x],i=idt(x);
if(isroot(y)) fa[x]=fa[y];
else add(fa[y],x,idt(y));
add(y,ch[x][!i],i);
add(x,y,!i);
pushup(y);
}
void splay(int x) {
pushall(x);
for(int y;y=fa[x],!isroot(x);rotate(x)) {
if(!isroot(y)) rotate(idt(x)==idt(y)?y:x);
}
pushup(x);
}
void access(int x) {
for(int p=0;x;p=x,x=fa[x]) {
splay(x);
ch[x][1]=p;
pushup(x);
}
}
void makeroot(int x) {
access(x);
splay(x);
swp(x);
}
void split(int u,int v) {
makeroot(u);
access(v);
splay(u);
}
void cut(int u,int v) {
split(u,v);
ch[u][1]=fa[v]=0;
pushup(u);
}
int findroot(int x) {
access(x);
splay(x);
while(pushdown(x), ls) x = ls;
splay(x);
}
主要就是下面这三个函数。分开讨论。
\(rotate\) 操作说明
因为 y = fa[x]，那么有 x = ch[y][i]。
旋转的过程即是先用 \(x\) 替换 \(y\)，即从 fa[y] 的视角而言。
然后用 \(x, y\) 两点间“包夹”的子树替换 \(x\)，即从 \(x, y\) 的包夹子树的视角而言。
最后将子树的位置用 \(y\) 替换，即从 \(x, y\) 间的视角而言。
\(splay\) 操作
这个主要是旋转方向的问题。
就是第一次有可能对父亲也有可能对自己，若自己与父亲呈一条线idt(y) == idt(x)则转父亲，此时是一个相对于 x <- fa[x] -> fa[fa[x]] 的较平衡形态 \(1\)，否则转自己，此时是 fa[fa[x]]->x->fa[x] 的直线形态 \(2\)。
发现无论怎样都需要将 x 再次旋至根，若原来为 \(1\) 形态，旋转后会变成 x -> fa[x] - > fa[fa[x]] 的形态，若原来为 \(2\) 形态，则旋转后会变为 fa[fa[x]] <- x -> fa[x] 的较平衡形态。
对了，还有当前只有一层深度，此时只用旋转 x 即可。
那么这样的话无论怎样都会出现一次较平衡形态，所以可以保证复杂度。
当然，这样只是便于记忆罢了。
严谨的分析其实可以用势能分析法，OI-Wiki 上有，等我学成归来……
然后我们再分析只有单旋的，若开始前是直线状态，则单旋两次后不会出现较平衡形态，而是先出现一个折线，再出现一条直线。
若开始前为折线，则单旋两次后先出现一条直线，再出现一个较平衡状态。
是的，所以若开始前为直线则不能保证复杂度。
同样，这也不是严谨分析……
\(access\) 操作
将 \(x\) 与 原树上的根 之间的路径取出。
注意点：
-
操作完后 \(x\) 有实儿子，但是只会有左儿子，即原树的到根的链上的节点，所以得到的是一条从 根 到 \(x\) 的链，没有其他节点。
-
pushup(x)