大家都知道 (好吧也许不知道) 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解决一下