LCT 的 link 这样子写是否正确
  • 板块学术版
  • 楼主Federico2903
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/7 19:33
  • 上次更新2024/4/7 19:34:48
查看原帖
LCT 的 link 这样子写是否正确
381949
Federico2903楼主2024/4/7 19:33

今天写题的时候复制了 LCT 的板子,写着写着感觉不对劲。我以前的 LCT 是这样写的。

inline void link(int x, int y) {
	makeRoot(x);
	if (find(y) != x) {
		fa[x] = y;
		siz2[y] += siz[x];
		pushup(y);
	}
}

但是这样 yy 不会出现不是 splay 根节点的情况吗。我以前拿这个板子写题都是没问题的,想了一会儿感觉没想懂。我觉得这样子写才是对的吧。

inline void link(int x, int y) {
	split(x, y); // makeroot + access + splay
	if (find(y) != x) {
		fa[x] = y;
		siz2[y] += siz[x];
		pushup(y);
	}
}
2024/4/7 19:33
加载中...