RT,突然想到了基于Splay的一种可能的实现方案:
实现splay的按权值分裂并将插入和删除进行改动即可:支持同一节点一次被删除多次(后者指节点的权值的出现次数)以及插入自带给定出现次数的节点(有相同的就合并)。至于合并,Splay可以做到单log的,按中序遍历插入即可(我想这个大家应该都知道吧2333)
其实改造后的FHQ-Treap也可以,但是单log合并太麻烦了不想弄
然后......按权值分裂写假了......因为没想明白怎么写照搬了FHQ-Treap的分裂,然后就RE了
请教这种实现方法的可行性,以及正确的按权值分裂Splay写法(网上找不到,按排名倒是会),提前感谢各位神犇