【求助】关于线段树分裂的不正经搞法
  • 板块学术版
  • 楼主2020kanade
  • 当前回复5
  • 已保存回复5
  • 发布时间2021/12/31 22:02
  • 上次更新2023/10/28 13:16:48
查看原帖
【求助】关于线段树分裂的不正经搞法
456724
2020kanade楼主2021/12/31 22:02

RT,突然想到了基于Splay的一种可能的实现方案:

实现splay的按权值分裂并将插入和删除进行改动即可:支持同一节点一次被删除多次(后者指节点的权值的出现次数)以及插入自带给定出现次数的节点(有相同的就合并)。至于合并,Splay可以做到单log的,按中序遍历插入即可(我想这个大家应该都知道吧2333)

其实改造后的FHQ-Treap也可以,但是单log合并太麻烦了不想弄

然后......按权值分裂写假了......因为没想明白怎么写照搬了FHQ-Treap的分裂,然后就RE了

请教这种实现方法的可行性,以及正确的按权值分裂Splay写法(网上找不到,按排名倒是会),提前感谢各位神犇

2021/12/31 22:02
加载中...