脚本宝典收集整理的这篇文章主要介绍了2021-8 清北学堂 省选 数据结构 内容回顾，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

主讲人：李欣隆

D1:

Treap(tree+heap)性质:每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质，复杂度 (O(nLOG n))。

旋转(rotate)有单旋和双旋, treap只需要单旋，这一点比较简单。

旋转时最好先记录每个点的编号，再断连，再重构，最后按照点的编号调用函数 update(x)。

Splay:每次对一个节点进行操作的时候通过―种方法把这个点旋转至根，称为Splay（伸展）操作。

注意：Splay要双旋

用单旋（单旋到根称为move to root）会被卡是常识了……对于单调数据，树会退化成一条链，然后每次move最深的点就被卡掉啦~

Splay：

sITuation 1:

先 fa 后 cur

situation 2:

两次 cur

Split：

Merge:

Fhq_treap:

先鸽着。

例题：

P4198 楼房重建

斜率预处理+线段树 (O(MLog^2n)) 维护。

D2:

D3:

D4:

D5:

脚本宝典总结

以上是脚本宝典为你收集整理的2021-8 清北学堂 省选 数据结构 内容回顾全部内容，希望文章能够帮你解决2021-8 清北学堂 省选 数据结构 内容回顾所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。