Luogu P14761 - CCD 的序列【动态序列统计】（之二）

在上一篇中，我们已经完成了整道题最关键的建模工作：
把“匹配关系发生变更”转化为区间统计问题。问题最终被化简为：在一个动态变化的序列上，支持区间查询与任意位置插入。

这一篇我们将会讨论：Splay 数据结构本身的功能与实现方式，以及它为什么适合承载这个问题。

1. Splay 是“自调整”的，而不是“显式平衡”的

在 AVL、SBT 等平衡树中，我们的核心目标是维护某种平衡条件。一旦条件被破坏，就通过旋转把树“修回来”。也就是说，平衡是目标，旋转是手段。

Splay 的思路是反过来的。它并不关心当前这棵树“是不是平衡”，而只关心一件事：把刚刚访问过的节点，拉到树的上层。

直观理解就是：
经常被访问的节点，就应该离根更近；这样后续再访问它，代价自然更小。因此在 Splay 中，访问本身，就是结构调整的理由。至于整棵树的形态是否平衡，并不是一个被显式维护的目标。

2. 什么是 splay 操作

splay(x) 的含义非常直接：
通过一系列旋转，把节点 x 拉到当前树的根节点（或某个指定节点之下）。

需要注意的是：

  • x 不一定是叶子；
  • 整个过程中可能发生多次旋转；
  • 每次旋转都只是普通的左旋或右旋。

Splay 的复杂性不在于旋转本身，而在于旋转顺序的选择。

3. Splay 中的三种经典旋转模式

设当前要 splay 的节点是 x，其父节点是 p，祖父节点是 g。根据 x、p、g 三者之间的位置关系，旋转会分为三种典型情况。

Zig（单旋）

当 p 本身就是根节点（即不存在祖父 g）时，只需要一次旋转。

此时旋转的目标非常明确：
让 x 成为新的根节点。

    p               x
   / \             / \
  x   C   ==>     A   p
 / \                 / \
A   B               B   C

旋转结束后，x 被直接提升到了根位置，这是最简单的一种情况。

Zig-Zig（同向双旋）

当 x 和 p 方向相同（同为左儿子，或同为右儿子）时，就会出现一条“歪着的链”。

        g
       /
      p
     /
    x

这种结构如果只旋一次，无法有效把 x 提到高位。因此需要连续两次旋转：

  1. 先旋转 p 与 g；
  2. 再旋转 x 与 p。

目标并不是单纯把 x 提到根，而是整体压缩这条同向的访问路径，让常访问的节点整体靠上。

        g                 g                  x
       / \               / \                / \
      p   D   (1)       x   D    (2)       A   p
     / \       ==>     / \       ==>          / \
    x   C             A   p                  B   g
   / \                   / \                    / \
  A   B                 B   C                  C   D

Zig-Zag（反向双旋）

当 x 和 p 方向相反时，结构呈现出“拧着”的形态：

        g
       /
      p
       \
        x

这种情况下，如果直接旋 p 和 g，结构会变得更糟。因此正确的顺序是：

  1. 先旋转 x 与 p；
  2. 再旋转 x 与 g。

目标是先把结构“拧正”，再把 x 提到更高的位置。

        g                 g                    x
       / \               / \                  / \
      p   D   (1)       x   D     (2)        p   g
     / \       ==>     / \        ==>       / \ / \
    A   x             p   C                A  B C  D
       / \           / \
      B   C         A   B

4. 为什么 Splay 不需要维护平衡条件

直观地看：

  • 如果一棵树长期非常“歪”，
  • 那说明你反复在访问某一侧的节点，
  • 而 Splay 会不断把这些节点旋转到上层，
  • 最终这条路径会被逐渐压缩。

因此，坏结构往往对应“不常用”的访问路径，而常用路径会被不断优化。这也是为什么：

  • 单次操作的复杂度可能很高；
  • 但在一整段操作序列上，Splay 的均摊复杂度是 O(log n)。

在竞赛环境中，这样的保证是足够可靠的。

5. 隐式 Splay 与普通 Splay 的区别

普通 Splay 是一棵标准的 BST，节点中有显式的 key，满足左小右大的性质。

而在本题中使用的是隐式 Splay。换句话说，节点本身不存 key，而是把整个序列按顺序映射到一棵 BST 的中序遍历上。

于是：

  • 中序遍历顺序 = 序列顺序；
  • 第 k 个元素 = 中序遍历第 k 个节点。

这样一来：

  • 查找第 k 个位置；
  • 在第 k 个位置插入；
  • 查询区间 [l, r]；

都可以统一转化为基于子树大小的树操作。

6. 区间信息的维护

在每个节点中，我们维护该节点所代表区间的信息。这一点与 AVL、SBT 等平衡树在旋转中维护区间信息并无本质区别。

旋转只会改变父子关系，不会破坏区间的连续性，因此只要在旋转后正确更新受影响节点的区间信息即可。

7. 为什么 push_up 是“三段合并”

在隐式 Splay 中，一个节点天然代表如下区间结构：

[ 左子树 ] + [ 当前字符 ] + [ 右子树 ]

因此在更新节点信息时，只需要按顺序合并这三段区间：

info = merge( merge(left, self), right )
size = size(left) + 1 + size(right)

每一次旋转结束后，只需对被下沉和被提升的节点各执行一次 push_up，区间信息就会自动恢复正确。

8. 总结

到这里，Splay 的功能与实现已经足够清晰了。

在本题中，Splay 本身并不承担复杂的逻辑，它只是提供了一种能够支持动态序列插入与区间定位的结构。真正与题目模型直接相关的，是节点中维护的区间信息及其合并方式。

Comments

comments powered by Disqus