splay 经典题目举例

发表于 分类于

数据结构专攻告一段落吧，把这段时间和以前做过的 splay 的题目拿出来晒晒，每题都写了一下简单的解题报告，每道题的做法最好要多花时间琢磨琢磨，splay 的题目主要就是中间过程的处理上比较麻烦。为了方便，我对区间操作都是将 l−1l-1 结点 splay 到根，r+1r+1 结点 splay 到根的右子树，定义根的右子树的左子树为关键结点。

常见的 splay 问题的处理

首先是标记，下放标记和上传标记最好分开写，否则的话非常容易出问题，我们下放标记记录的是孩子结点的信息，所以我们如果要对一个结点打标记，我们要先处理好这个结点，比如说这个结点权值加上一个值，左右子树交换等等。

其次是区间操作上的方便性问题，对于平常的区间操作，如果每次询问都是删除 [l,r][l, r] 区间，这样我们可以在序列左右两端加上两个哨兵，这样处理起来方便，但是有的题目这样反而不好处理，比如翻转下标小于 x 的所有数，这样左边界不能成为翻转的对象。

最后是比较重要的一点，就是如果减少时间的开销，一般我们对 splay 做 insert 操作的时候，我们要将加入到结点，或者子树的根结点 splay 到根，这样我们可以防止 splay 出现退化的情况，虽然这样还是会退化，但是均摊复杂度是可以接受的。

HDU3487  Play with Chain

http://acm.hdu.edu.cn/showproblem.php?pid=3487

大致题意

给你一个序列，有两个操作，一个是把一段区间翻转，另外一个是把一段区间截下来放到另外一个位置，问你最后的序列长什么样。

对于 FLIP 操作直接将 l−1l-1 和 r+1r+1 位置的结点伸展，然后在关键结点出将标记处理了。

对于 CUT 操作，首先我们将关键子树分离，记得分离之前要 pushdown 关键根，然后将关键子树接到新的子树上去，注意这时候我们要记得将关键子树的父亲结点设为关键根，然后对关键根进行 update 操作。

NOI2005 维护数列

这题巴蜀的 OJ 挂掉了，现在没办法交，不过题目还是很有意思的，给你一个数列问你一系列的关于数列的问题，除了区间翻转以外的问题都可以转化为线段树来做，我们可以先将线段树想清楚，然后转化成 splay 的模型就可以了。

利用 splay 来维护整个序列，最大子字段和注意一下需要处理的是必须至少选一个，所以我们加入的哨兵还有空结点的所有特征值为负无穷大，例外的是空结点的 sizesize 域以及和值应为 00。

至于平衡树的处理，标记都是下放，特征值一定都是向上传递的，写的时候不要写错，此外要注意这题懒操作要写好，否则会 TLE。

当时 WA 了一天，主要错的地方在于没有处理好哨兵的特征值，此外一定要注意我们可以把哨兵统一到结点中，只要其特征值取的好。

本题注意全部数字都是负数的情况。

POJ3580  Super Memo

http://poj.org/problem?id=3580

这题也是比较经典的入门题了，模型很裸，但是写起来要纠结一点儿。

这题和常规的 splay 题类似，唯一的区别就是那个区间旋转，我们可以找到分界点，然后左半边右半边进行一次 reverse，然后整个区间再进行一次 reverse。

NOI2003 文本编辑器

很多 OI 选手津津乐道的题目，这题可以算是相当恶心的题目了，给你一个文本编辑器的模型，叫你模拟全部的操作，直接用 splay 来维护，然后加一个指针，表示现在光标的位置。

标准的 splay 题，注意这题 delete 和 get 可能会越界，要判断，旋根的时候右边界必须是 size−1size-1。

此外数组要开足够大，开 10242×21024^2 \times 2 差不多。注意中间的处理不要写的太复杂，否则写挂了也不好处理。

HDU1890 Robotic Sort

http://acm.hdu.edu.cn/showproblem.php?pid=1890

大致题意

这题是给你一些不同的数，每次选择最小的翻转回它应该在的位置，叫你模拟这个过程。这题最后要保证相同数字的相对位置不变。

经典 splay 问题，我们可以考虑记录每一个高度对应的结点的指针，用一个数组存起来，然后每次将其旋转到根，根的左子树加上 ii 加上 11 当做答案，然后翻转左子树，删除根结点。

注意为了操作时产生不必要的麻烦，建议不加哨兵，删除根的时候特判一下，如果有左右孩子，那么就去找前驱后继，删除，否则直接 root 替换即可。

FZU1978 Repair the brackets

http://acm.fzu.edu.cn/problem.php?pid=1978

给你一个括号序列，动态更新区间，包括区间取反，区间翻转，区间赋值，查询使得一个区间变成规则括号串的最小花费，对于一个位置把括号反向，需要 11 的花费。

利用 splay 来维护全部的操作，定义左括号是 11 右括号是 −1-1，对于一个 Query，我们计算区间从左到右的和值最小值，记录 aa 为这个最小值的绝对值，bb 为这个区间的和减去这个最小值，那么答案就是⌈a2⌉+⌈b2⌉\lceil\frac{a}{2}\rceil+\lceil\frac{b}{2}\rceil，注意都是上取整。

由于需要进行区间的翻转，所以要记录右边的值，此外由于有区间的取反，所以要记录最大值。

最后需要注意的是最小值不超过 00，最大值不小于 00。

HDU2475 Box

http://acm.hdu.edu.cn/showproblem.php?pid=2475

给你一些盒子的相对关系，动态的对盒子进行合并、拆分，问你某个盒子最外层的盒子是什么。这题是经典的括号序列问题，如果不懂的，可以去百度一下，应该有相关的资料～

利用 splay 来维护括号序列，对于一个 DFS 序列，我们入栈记录一次，出栈记录一次，我们用 x 表示 x 这个结点入栈的点，用 x+nx+n 表示 xx 出栈的点，那么对于这个问题可以轻松转化过来。

对于 MOVE 操作，如果可以移动，我们进行 cut 操作和 add 操作。

对于 cut 操作，我们将 xx 和 x+nx+n 分别旋根，这样我们可以得到一个 xx 和 x+nx+n，x+nx+n 是根，xx 是其左子树的某一个结点，这样 xx 的左子树和 x+nx+n 的右子树是无效的，我们剪掉它们，并且将 x+nx+n 的右子树接到 x 的左子树最后，接着把 x+nx+n 旋根，保证平衡性。

对于 add 操作，我们将新的父亲结点旋到根，x+nx+n 旋到根，然后进行连接，注意新的父亲结点的右子树，需要接到 x+nx+n 的右子树上去。

对于初始化，我们可以确定每一个结点的父亲结点，然后逐个进行 add 就是。

最后的问题就是如何判断 yy 是不是 xx 的子树，这个的判断方法是先对 xx 执行 cut 操作，注意这时候两个子树不要合并，然后再去查询 yy 的根结点，如果 yy 的根结点是 xx，说明 yy 是 xx 的子树，最后记得复原。复原的时候要把 xx 和 x+nx+n 旋根，两个子树旋根，然后拼接。

查询一个结点的根结点，其实就是 DFS 序列的起点，也就是所在树的最小元素，将 xx 旋根，找左子树的最小值即可。

HDU3726 Graph and Queries

http://acm.hdu.edu.cn/showproblem.php?pid=3726

给你一个图，有一些无向边，现在有三种操作，一个是改变点权，一个是删掉一条边，一个是查询结点 x 所在连通块第 kk 大的点权。

我们离线从后向前处理，对于每一个删边操作相当于是一个合并操作，然后对于每一个点来说，我们拉一个邻接表表示修改的权值。那么，对于每一个修改操作我们就将节点 splay 到根，然后删掉根结点，修改根结点，然后把结点加入树中。