一个非常有趣的问题
查看原帖
一个非常有趣的问题
238408
vectorwyxSD省选加油楼主2021/1/24 12:06

RT,我是用splay过的这题。代码里的 rotate 函数是这样写的:

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] 的前面才对。但我按照上面所写的代码通过了本题,那么到底是本题数据过水还是另有原因?求巨佬解答,万分感谢!

2021/1/24 12:06
加载中...