这样写真的是对的么?

P3391 【模板】文艺平衡树

Orina_zju @ 2018-04-08 16:10:17

我看题解区好多标程都是这样写旋转函数的:

int old=f[x],oldf=f[old],which=get(x);
    pushdown(old); pushdown(x);//不要忘记pushdown 

其中get函数用于确定x是父节点的哪个孩子。

但如果pushdown(old)时发生了交换,x和f[x]的位置关系改变,那么此时的which是不是错误的信息呢?

对于本题,在进行splay(x)之前,用于求第k大的kth函数已经将沿途的所有标记都清理了,所以上述的问题不会造成影响,不过我还是觉得这样写不够严密。


by Mirach @ 2018-04-08 16:24:24

可是就如你所说,找到它时已经把标记清理过了,那么这个pushdown函数都不一定有存在的意义,只是为了万一万一万一WA了调试不出来

(⊙v⊙)用了以后更安心


by DyingShu @ 2018-09-19 20:03:02

我也觉得有点不对,应该是要pushdown之后再确定父子关系吧@Orina_zju


|