模板 - 数据结构 - 可持久化无旋Treap/PersistentFHQTreap
有可能当树中有键值相同的节点时，貌似是要对Split和Merge均进行复制的，本人实测：只在Split的时候复制得到了一个WA，但只在Merge的时候复制还是AC，可能是恰好又躲过去了。有人说假如确保键值唯一，或者在一个节点保存相同键值的多个点的实现，则只需要在其中一个进行复制，因为从根到达叶子的路径是唯一的，但假如有多个点，分裂操作把这些权值相同的点分成两部分，而在插入/删除节点之后有可能会使得一棵树的形态改变（基于随机优先级），这些权值相同的点未必是Split时复制出来的那几个。暂时没有想明白，会不会是把权值相同的点丢到另一棵树上就没事了？不过这样貌似搞得越来越复杂了，假如因为重复点的原因导致双重拷贝爆空间的话可以求助于其他数据结构，例如不强制在线的话可以使用可持久化权值线段树。
需要注意的是Treap系列平衡树不好的地方在于它的复杂度是期望的而不是稳定的，脸不好的话随机出来的是一条链（或者深一点的链），这个时候时间性能奇差，空间也会因为可持久化而复制太多节点（大概是logn的几倍！）。在比赛可以srand(time(0))，但是在CF这样做可能就FST了。总之缺点很多的，多学几种数据结构对比使用吧。
简单来说，可持久化无旋Treap解决了强制在线询问第t个版本的第k大/前k大和的名次树问题，但如果涉及的k的值域是在（线段树）可接受的范围的，也就是说“不需要进行离散化”的，例如 [CF#602 D2] 中要求实现的是一个可持久化数组（每次询问数组第t个版本的第k个元素，也就是序列意义的第k大），就使用可持久化权值线段树解决。当t的值是升序或者离线询问之后变成升序，则不需要可持久化数据结构，用相应的普通版本即可。
参考资料：
可持久化平衡树详解及实现方法分析 - chy_2003 - 博客园
最新文章
- c语言快速入门2
- 两个div叠加触发事件发生闪烁问题
- 基于 Annotation 拦截的 Spring AOP 权限验证方法
- CentOS 6.5下配置iSCSI网络存储
- poj: 1003
- POJ 2023 Choose Your Own Adventure（树形，dfs，简单题）
- 在stm32上移植wpa_supplicant（一）
- 拖动滚动条时某一处相对另一处固定不动(position:fixed)
- MySQL 删除数据库中反复数据（以部分数据为准）
- html2canvas 识别 svg 解决方案
- MVC，MVP和MVVM三种开发模式
- git fetch 和git pull 的差别
- Android ListView滚动到指定的位置
- bzoj1208splay模板题
- Outlook 2007 实现自动添加密送的方法
- win10 WiFi 密码查询 命令
- Fzu软工第二次作业-词频分析
- python迭代器、生成器、装饰器
- 机器学习之路： python 朴素贝叶斯分类器 MultinomialNB 预测新闻类别
- [iOS]过渡动画之高级模仿 airbnb