一个关于 Splay 的玄学问题
  • 板块学术版
  • 楼主时律
  • 当前回复5
  • 已保存回复5
  • 发布时间2022/1/19 20:48
  • 上次更新2023/10/28 11:54:20
查看原帖
一个关于 Splay 的玄学问题
123026
时律楼主2022/1/19 20:48

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 的写法就是对的,所以我觉得可能是在这里出了问题,不过始终找不到具体是哪里。

求好心人帮忙看看)

2022/1/19 20:48
加载中...