是数据太水还是我很正确

P3391 【模板】文艺平衡树

ducati @ 2021-01-26 16:32:47

//pushup: update the size of a node
//ducati loves splay
void Rotate(int x){
    int y=f[x],z=f[y],t=ge(x);
    pushdown(x),pushdown(y);
    tree[y][t]=tree[x][t^1],f[tree[y][t]]=y,tree[x][t^1]=y,f[y]=x,f[x]=z;
    if (z)  tree[z][(tree[z][1]==y)]=x;
    pushup(x),pushup(y);
}

上面是Splay旋转操作的代码。

这里有一个非常致命的问题: pushup(x),pushup(y)的顺序。经过旋转后，此时x是y的父节点，先更新x后更新y会导致x的数据错误。

结果我A了……不信看提交记录……

所以是数据太水还是我很正确？

by k2saki @ 2021-01-26 16:35:02

草？

by k2saki @ 2021-01-26 16:35:46

之前 LCT 板子交换也不会挂，但是按道理是不能交换的啊？

或者我的理解有一点偏差。

by ducati @ 2021-01-26 16:36:22

@ReBinary 请问您是想草这个数据还是想草我程序？（数据太水还是我很正确）

by ducati @ 2021-01-26 16:36:38

@ReBinary 我也这么想的呀

@巨佬

by ez_lcw @ 2021-01-26 16:42:54

@ducati 反正你下一次 rotate 的时候也会把 x 再更新一遍

然后在 Splay 最后再把当前点更新一遍就好了

by k2saki @ 2021-01-26 16:43:35

以前学 splay 貌似看一个写过不需要 splay(x)？

可能我记岔了

by ducati @ 2021-01-26 16:45:08

@ez_lcw 收到

by 天命之路 @ 2021-01-26 17:16:32

还有就是 rotate 的时候不需要 pushdown

只有在查找结点的时候需要，因为是先找到节点再 Splay

by ducati @ 2021-01-27 09:27:50

@天命之路为啥？~~计蒜客就这么说的~~

by ducati @ 2021-01-27 09:29:06