`A: A.cpp:93`: `int rank_of(int)`: Assertion `BST[child[now][1]] != BST[now]` failed.
非旋 Treap 真的需要在每个结点记录值出现次数(`times[]`)吗? 非旋 Treap 的插入是基于分裂/合并的,应该是没有办法维护每个数字的出现次数的,你这平衡树建出来的状态大概就是一堆带有相同数据的结点,然后这些结点上分别标记了他们的出现次数…
BST 的结构确实可以维护 但是你在查询的时候会很麻烦吧,我 `assert` 了你的 `rank_of`
```cpp
if(target==BST[now])
return res+size[child[now][0]]+1;
```
这里无法保证 now 的值小于 右儿子的值 这是你想要的吗?
建议不要记录每个几点值得重复次数,然后尽量让查询操作依赖 `merge` 和 `split` 操作,要不然非旋 Treap 就没好写的优势了…
要板子吗? [QAQ](https://shuyumo2003.github.io/%E3%80%8C%E5%AD%A6%E4%B9%A0%E6%80%BB%E7%BB%93%E3%80%8D%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/#%E9%9D%9E%E6%97%8B%20Treap)
by ShuYuMo @ 2021-03-16 07:25:05
@[ShuYuMo](/user/44615) 我只是顺手拷了板子;
所以为啥没办法保证值相同的结点放在一起呢
?
QWQ
by 白鲟 @ 2021-03-16 16:21:17
@[ShuYuMo](/user/44615) 其实可以维护每个数字的出现次数,只需要插入的时候分裂成三棵树。
不过意义不大。
还是依赖 `merge` 和 `split` 方便,谢谢啦!
QWQ
by 白鲟 @ 2021-03-16 16:55:52
插入的时候分成三棵树应该可以… 但是没啥用了…
```cpp
void insert(int target)
{
int x=0,y=0;
split(root,x,y,target);
if(BST[y]==target)
{
++times[y];
root=merge(x,y);
}
else
{
int now=++total;
times[now]=size[now]=1;
priority[now]=rand();
BST[now]=target;
root=merge(x,merge(now,y));
}
return;
}
```
你这个插入,按照 target 分裂出来的第二棵平衡树,最大值可能的确是 target,但是最大值不一定在根上好吧
Treap 最核心优势不就是好写吗… Splay这种东西只有 LCT 的时候才写吧 ……
by ShuYuMo @ 2021-03-16 19:31:45