splay 删数,如果把两个 pushup 调个顺序也能 AC,为什么啊()
void del(int w){
int p1=pr_p(w),p2=nx_p(w);
splay(p1);
splay(p2,p1);
int p=tr[p2].ch[0];
tr[p].cnt--;
tr[p].siz--;
if(!tr[p].cnt){
clear(p);
tr[p2].ch[0]=0;
}
pushup(p2);
pushup(p1);
}
先把要删的数 w 的前驱 p1 splay 到根,再把 p2 splay 成 p1 的右子节点,然后删掉 p2 的左子节点,没啥问题
更新信息的时候因为 p2 是 p1 的子节点,所以应该先 pushup p2 再 pushup p1 才对啊()