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