[内容有误] 后缀平衡树参考代码被 hack

[JellyQuark]

请选择：

• 我正在着手修复这个问题

我正在访问这个页面

https://oi-wiki.org/string/suffix-bst/

我发现页面有这样的问题

参考代码 wa 了，hack 数据：

29
QN
QUERY Q
ADD QNNNQNQQQN
ADD NNQQQNNQQNQNQNNNQQQ
ADD QNNNQ
QUERY NQQQNQQNQQQQQQQNNNNNNNNQN
DEL 7
ADD QNNQ
QUERY QNQQNNNNNQQQNQNNQQNQ
QUERY NQQQNQNQQNNQNQN
QUERY QNNQNNNQNQNQQQNQQNNNQQNNQQNNQQQQN
QUERY NQNQN
QUERY QNQNNQN
ADD QQN
ADD NQ
ADD QNQNQ
ADD NNQQNNQQNQ
QUERY QNQNNQNNQQQQQQNQQNNNQNNQNQNQQNNQNNQNNNNNQNQQQNQQQQ
QUERY QQQQNQNQQNNQNQQQNNNQQQQNNQNQNQNQNNQQQNNNNN
ADD NNQQNNQQNQ
ADD QQNNNQQQNQQNNN
ADD NQQNNQ
ADD NNQNQNNQQNQ
ADD NQNQNQQN
ADD QNQNNQQNQNNNQNNQQNQQ
DEL 1
QUERY NQQQNQQNNNNNQNQQQNNNQQQNQQNQQNNQQNNNNNQQ
DEL 4
ADD NQNQQNQNQN
QUERY QQNQNQNNQNQNNQQ

最后一个输出正确答案为 35，参考代码输出为 37。

暂时没时间帮忙 debug，希望有其他人修（

[welcome]

感谢你对 OI Wiki 的关注！记得在 Issue 中表达清楚自己的意思哦～

[JellyQuark]

UPD：参考代码在第 $109$ 行到 $111$ 行有误，正确代码应为：

        R[fa] = L[nrt];
        L[nrt] = L[rt];
        R[nrt] = R[rt];

[Enter-tainer]

来个pr？

[JellyQuark]

来个pr？

等下，我再确认一下有没有其他问题（我这还是拍挂了）

[JellyQuark]

UPD：我发现似乎用 SGT 来维护后缀平衡树的思路是非常假的，主要问题在于删除操作后没有能够快速保证 tag 合法的维护方式。我粗略考虑了一下感觉懒惰删除似乎是可行的，但代码需要进行大改。

[HeRaNO]

可以参考 The suffix binary search tree and suffix AVL tree 这篇论文对这个页面重构一下。陈立杰论文里面的描述有点简略，并且没有参考文献，感觉应该谨慎选择。

[ImpleLee]

我感觉tag等价于从根到叶子的路径，所以要让tag有效就等价于其路径在合法的时间内不变，所以采用完全不旋转的sgt吧。
删除可能也要用完全不旋转的方案？

[ImpleLee]

*根到叶子的路径完全不会被改动的方案。

[JellyQuark]

是的，所以这种方案就是懒惰删除😂

[ImpleLee]

我在 #5083 里用的是积极删除，因为这个场景其实很难懒惰（因为每个节点需要和序列的位置对应）。你可以看看？