很多时候 Splay 的 pushdown 都是这么写的,pushdown 放在了 rotate 里面:
inline void rotate(int i)
{
int f=t[i].fa,gf=t[f].fa;
pushdown(f),pushdown(i);
...
}
inline void splay(int x,int y=0)
{
for(int f;(f=t[x].fa)!=y;rotate(x))
if(t[f].fa!=y)
rotate(which(f)==which(x)?f:x)
}
但是在 LCT 里则必须提前把 x 到根的路径全部 pushdown,在 rotate 里 pushdown 是错的。
然而一般的 Splay 写法既可以在 rotate 里 pushdown,也可以提前 pushdown 整个路径。
请问这是为什么?