一个非常有趣的问题

P3391 【模板】文艺平衡树

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。


|