[询问]分裂合并treap对于重复节点,通常分开还是加一个cnt字段并在一起?

P6136 【模板】普通平衡树(数据加强版)

butterfly123 @ 2022-06-23 20:17:45


by 我是人999 @ 2022-06-23 20:28:16

@butterfly123 分开的话方便按排名分裂


by butterfly123 @ 2022-06-23 22:03:15

@我是人999 题解中那个旋转的treap和splay又是并在一起写的,插入的时候cnt++。只有无旋treap比较特殊嘛?


by 我是人999 @ 2022-06-23 22:06:46

@butterfly123 是的。并且我认为是因为 FHQ-Treap 按排名分裂操作的关系,所以要分开存。(我的理解可能有误)


by butterfly123 @ 2022-06-23 22:48:56

@我是人999 好滴,感谢


|