今天写题的时候复制了 LCT 的板子,写着写着感觉不对劲。我以前的 LCT 是这样写的。
inline void link(int x, int y) {
makeRoot(x);
if (find(y) != x) {
fa[x] = y;
siz2[y] += siz[x];
pushup(y);
}
}
但是这样 y 不会出现不是 splay 根节点的情况吗。我以前拿这个板子写题都是没问题的,想了一会儿感觉没想懂。我觉得这样子写才是对的吧。
inline void link(int x, int y) {
split(x, y);
if (find(y) != x) {
fa[x] = y;
siz2[y] += siz[x];
pushup(y);
}
}