社区讨论

一个非常有趣的问题

vvectorwyxSD省选加油
P3391【模板】文艺平衡树参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@locphvv6
此快照首次捕获于
2023/10/30 17:37
2 年前
此快照最后确认于
2023/11/05 04:28
2 年前
查看原帖
RT，我是用splay过的这题。代码里的 rotate 函数是这样写的：
CPP
inline void rotate(int x){
	int y=fa[x],z=fa[y],sx=son(x),sy=son(y),b=ch[x][!sx];
	push_down(y);push_down(x);//这里出了一个小差错
	if(z) ch[z][sy]=x; else root=x;fa[x]=z;
	ch[x][!sx]=y;fa[y]=x;
	ch[y][sx]=b;if(b) fa[b]=y;
	push_up(y);push_up(x);
}
很显然push_down(y) 会改变 ch[x][!sx] 的值，因此它应该放到 b=ch[x][!sx] 的前面才对。但我按照上面所写的代码通过了本题，那么到底是本题数据过水还是另有原因？求巨佬解答，万分感谢！

回复

共 4 条回复，欢迎继续交流。

正在加载回复...