关于splay的一点问题
  • 板块学术版
  • 楼主滑大稽
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/8/19 10:55
  • 上次更新2023/11/6 19:57:32
查看原帖
关于splay的一点问题
203743
滑大稽楼主2020/8/19 10:55

大家都知道 (好吧也许不知道) splay的删除可以把一个树的前驱转到根节点,再把后继转到前驱下面,后继的左子树就一定是要被删除的那个数。比如这样(请原谅我奇怪的变量名):

inline void sc(int x)
{
	int front=qh(x,0),back=qh(x,1);
	splay(front,0);splay(back,front);
	int a=q[back].c[0];
	if(q[a].t>1)
	{
		q[a].t--;
		splay(a,0);
	}
	else q[back].c[0]=0;
}

然后我假如先旋转后继到根节点,再旋转前驱到根节点下面,按理说前驱的右字树就是要删除的那个树,就是这样的:

inline void sc(int x)
{
	int front=qh(x,0),back=qh(x,1);
	splay(back,0);splay(front,back);
	int a=q[front].c[1];
	if(q[a].t>1)
	{
		q[a].t--;
		splay(a,0);
	}
	else q[front].c[1]=0;
}

然后这样打我就wa了,换成第一种方式就对了

不知道是为什么,调试了一下,第一种删除后那个数变成了inf,对排名没影响,第二种变成了-inf,就有影响了。

望众dalao解决一下

2020/8/19 10:55
加载中...