关于标记下传,节点信息维护顺序的疑惑...
查看原帖
关于标记下传,节点信息维护顺序的疑惑...
58747
windinsoul楼主2022/4/18 16:25

如题,在单旋转时,我对标记下传和节点信息更新的顺序感到疑惑,我个人认为旋转前标记下传时应该先下传父节点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);
    }
2022/4/18 16:25
加载中...