做 P3224 [HNOI2012]永无乡 时,我写的 Splay 一直调不出来,后来才发现是这么一个问题:
(先贴完整代码)
在 insert
函数里面有这么一段:
if(p==0)
{
int t=newnode(x,0);
root=t;
return;
}
但当我把它写成这样的时候,它就是错的:
if(p==0)
{
root=newnode(x,0);
return;
}
我自然想到了强制类型转换,但是 newnode
是这样的:
inline int newnode(int val,int fa)
{
node s;
s.fa=fa,s.val=val,s.sum=1,s.ch[0]=s.ch[1]=0;
tree.push_back(s);
return int(tree.size())-1;
}
甚至里面 tree.size()
都已经转化成 int
类型了,所以我并不明白发生了什么。
另外,后来在我写 P3380 【模板】二逼平衡树(树套树) 的时候,也发现了同样的问题。
不过这两道题有一个共性:我都是定义了 Splay
类型并且开了一个 Splay
数组,而我平常写其他题用 Splay 时第二种 insert
的写法就是对的,所以我觉得可能是在这里出了问题,不过始终找不到具体是哪里。
求好心人帮忙看看)