是这样的。
我刚学替罪羊树,里面有一个可实现函数,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 到底是为什么,求诸位大佬解答,或是给我一个能解答它的网址。