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