神秘疑问
查看原帖
神秘疑问
555301
zfx_VeXl6楼主2024/11/29 15:23

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 才对啊()

2024/11/29 15:23
加载中...