求助关于splay函数的标记下传
查看原帖
求助关于splay函数的标记下传
88028
LastOrder_楼主2021/11/2 18:43

RT,萌新刚学splay,求助为什么splay里必须写pushdown?

这是wa(样例也过不去的代码)

inline void splay(int k, int lim = 0){
	for(int fa = f[k] ; (fa = f[k]) != lim ; rotate(k))
		if(f[fa] != lim)
			get(fa) == get(k) ? rotate(fa) : rotate(k);
	if(!lim) rt = k;
}

这是AC代码

inline void splay(int k, int lim = 0){
	for(int fa = f[k] ; (fa = f[k]) != lim ; rotate(k)){
		pushdown(f[fa]), pushdown(fa), pushdown(k);
		if(f[fa] != lim)
			get(fa) == get(k) ? rotate(fa) : rotate(k);
	}
	if(!lim) rt = k;
}

另外,为什么在文艺平衡树里,pushdown()splay() 都不需要下传标记?

2021/11/2 18:43
加载中...