关于替罪羊树
  • 板块学术版
  • 楼主linjunye
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/11 22:25
  • 上次更新2024/8/12 08:54:39
查看原帖
关于替罪羊树
745970
linjunye楼主2024/8/11 22:25

是这样的。

我刚学替罪羊树,里面有一个可实现函数,find_kth。

也有一个可实现函数 del_kth。

然后我寻思着,这两者代码应该是差不多的。

但我翻了翻《算法竞赛》,发现:

find_kth 函数中写道:

if(T[T[p].ls].siz>=k)p=T[p].ls;

而 Del_kth 函数中写道:

if(T[T[p].ls].siz+T[p].del>=k)Del_k(T[p].ls,k);

本来以为是作者习惯,但在网上,洛谷题解中也都是加了 T[p].del。

会不会加上对答案有影响?然后我把 T[p].del 也删了,又交了一遍 P6136,但也能 AC。

所以加上 T[p].del 到底是为什么,求诸位大佬解答,或是给我一个能解答它的网址。

2024/8/11 22:25
加载中...