vectorwyx @ 2021-01-24 12:06:25
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]
的前面才对。但我按照上面所写的代码通过了本题,那么到底是本题数据过水还是另有原因?求巨佬解答,万分感谢!
by vectorwyx @ 2021-01-24 12:12:16
这里是完整的代码
by Semsue @ 2021-01-24 12:20:32
这个应该不会影响正确性吧。。。
by vectorwyx @ 2021-01-24 12:25:56
@Flying_Bird 为什么啊?
by 传奇666666 @ 2021-01-24 12:47:10
其实可以按照LCT的写法,先提前把所有都pushdown一下,然后再rotate。不过正常的splay其实不需要在rotate里写pushdown。