求问关于splay的pushdown
  • 板块学术版
  • 楼主ExplodingKonjac
  • 当前回复11
  • 已保存回复11
  • 发布时间2021/11/3 08:01
  • 上次更新2023/11/4 01:32:11
查看原帖
求问关于splay的pushdown
279800
ExplodingKonjac楼主2021/11/3 08:01

很多时候 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 里则必须提前把 xx 到根的路径全部 pushdown,在 rotate 里 pushdown 是错的。

然而一般的 Splay 写法既可以在 rotate 里 pushdown,也可以提前 pushdown 整个路径。

请问这是为什么?

2021/11/3 08:01
加载中...