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 噢噢 懂了 谢谢