Splay 学习笔记

Splay 是一种由 Tarjan 发明的，可在不维护额外信息的情况下动态平衡，且可合并的数据结构。

基本操作

将一个结点 $u$ 向上旋转。

不是一般性地，设 $u$ 是其父亲 $f$ 的左儿子。则操作后 $f$ 的父亲变为 $u$，$u$ 的父亲变为 $f$ 的原父亲，$u$ 的右儿子变为 $f$，$u$ 的右子树成为 $f$ 的左子树。右儿子的情况是对称的。

将一个结点 $u$ 不断旋转到根。

一种平凡的想法是不断地将其上旋。这种做法有一个显著的问题：如果原树有一条长链，那么经过操作后这条长链依然存在（有可能成为一条长路径），不够优秀。

一个简单的解决方案是这样子：将父亲一并考虑，如果父亲存在且与自己类型相同，那么先旋转父亲，否则先旋转自己。处理完这个后再旋转自己。这种做法可以将长链上的结点变得“更多分叉”，使得复杂度正确。

为了保证复杂度正确，我们需要在每次操作后都保证调用的目标结点成为了根。

暴力插入，然后 Splay。

先让 $u$ 成为根。如果左右子树不是都非空，那么做法是平凡的；否则找到左子树的最大值并将其旋转到左子树的根（实际编写可以利用 Predecessor 函数找到 $u$ 的值的前驱），并将右子树直接连接到左子树的根的右儿子上。

就像 BST 一样查询，最后 Splay 即可。

维护一个 multiset，支持 Insert 到 nth 的六种名次树基本操作，操作数 $\le 10^5$，值域为 $[-10^7,10^7]$。

翻转一个区间。

让 $l-1$ 成为根，$r+1$ 成为它的右儿子。$r+1$ 的左儿子即为 $[l,r]$ 的树。直接打翻转标记。

为了避免分类讨论，通常会添加 $0$ 号结点与 $n+1$ 号结点。

给定一个序列，进行 $q$ 次 Reverse 后求最终序列。$n,q\le 10^5$。