关于标记下传,节点信息维护顺序的疑惑...

P3391 【模板】文艺平衡树

windinsoul @ 2022-04-18 16:25:04

如题,在单旋转时,我对标记下传和节点信息更新的顺序感到疑惑,我个人认为旋转前标记下传时应该先下传父节点y,再下传子节点p,然后维护节点信息时应该先更新旋转后的子节点y再更新新的父节点p。\ 也就是第一份代码中那样,但是不管提交哪一种顺序的代码都能AC,题解中的代码似乎也各种顺序都有--,所以标记下传和节点维护的顺序是否会影响答案的正确性QAQ?

 void rotate(int p){
        int y=fa[p],r=fa[y];
        pushdown(y), pushdown(p);
        int yson= which(p),rson= which(y);
        connect(ch[p][yson^1],y,yson);
        connect(y,p,yson^1);
        connect(p,r,rson);
        maintain(y);maintain(p);
    }
void rotate(int p){
        int y=fa[p],r=fa[y];
        pushdown(y), pushdown(p);
        int yson= which(p),rson= which(y);
        connect(ch[p][yson^1],y,yson);
        connect(y,p,yson^1);
        connect(p,r,rson);
        maintain(p);maintain(y);
    }
 void rotate(int p){
        int y=fa[p],r=fa[y];
        pushdown(p), pushdown(y);
        int yson= which(p),rson= which(y);
        connect(ch[p][yson^1],y,yson);
        connect(y,p,yson^1);
        connect(p,r,rson);
        maintain(y);maintain(p);
    }
 void rotate(int p){
        int y=fa[p],r=fa[y];
        pushdown(p), pushdown(y);
        int yson= which(p),rson= which(y);
        connect(ch[p][yson^1],y,yson);
        connect(y,p,yson^1);
        connect(p,r,rson);
        maintain(p);maintain(y);
    }

by reveal @ 2022-04-18 20:20:25

这个问题是这样的,如果是一般平衡树的话操作是自顶向下进入的,只要进入时 pushdown 了 rotate 是不需要的。

pushup 其实同理。

但是 LCT 不满足所以还是那啥一点为好


by windinsoul @ 2022-04-18 20:53:46

@reveal 噢噢 懂了 谢谢


|