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

1. 题意概述

题目要求维护一个动态变化的合法括号序列。

初始时序列为空。接下来进行 $n$ 次操作，每次操作给定两个整数 $(l, r)$（$0 \le l \le r \le |S|$），表示：

在当前序列的第 $l$ 个插入位置插入一个左括号 '('；
在当前序列的第 $r$ 个插入位置插入一个右括号 ')'。

题目保证：每次操作完成后，整个括号序列仍然是合法的。

匹配关系与“匹配发生变更”

在一个合法括号序列中，每个括号都有且仅有一个与之匹配的括号，匹配关系由括号的嵌套结构唯一确定。

若某个括号在一次操作前匹配的是括号 $A$，在操作后匹配对象变为括号 $B$（且 $A \neq B$），则称该括号的匹配发生了变更。

本题的核心问题

在每一次插入操作完成后，需要输出：

由于本次操作导致匹配对象发生变化的旧括号数量
（不包括本次新插入的两个括号）

2. 题目分析与建模：从匹配变化到区间统计

本题的关键不在于维护“谁和谁匹配”，而在于如何刻画“哪些匹配会发生变化”。

插入操作的结构本质

一次操作在原括号序列 $S$ 上同时插入一对新括号 '(' 和 ')'，并保证新序列仍然合法。

从结构角度看，这等价于：

在原序列中，将一段连续子串整体包裹进一层新的括号中。

给定操作 $(l, r)$，被包裹的原有区间为：

$$ (l+1,\ r) $$

哪些括号的匹配会发生变化？

将原序列中的括号按其位置与匹配关系分类，可以发现：

完全位于区间 $(l+1, r)$ 外的括号，匹配关系不变；
匹配对象也完全位于区间 $(l+1, r)$ 内的括号对，匹配关系不变；
一端在区间内、另一端在区间外的匹配对，其匹配关系一定会发生变化。

因此可以得到结论：

一个旧括号的匹配发生变更，当且仅当它原本匹配的括号与它位于区间 $(l+1, r)$ 的不同侧。

转化为区间统计问题

于是，原问题可以被精确地重述为：

在原括号序列中，统计区间 $(l+1, r)$ 内，有多少括号是与区间外的括号直接匹配的。

为此，引入两个区间统计量：

$open$：区间内无法在区间内部完成匹配的左括号数量；
$close$：区间内无法在区间内部完成匹配的右括号数量。

显然：

$open$ 个左括号必然向区间右侧寻找匹配；
$close$ 个右括号必然向区间左侧寻找匹配。

因此，跨区间匹配对的数量为：

$$ open + close $$

而每一对这样的匹配，会导致两个旧括号的匹配关系发生变化。

核心公式

设区间 $(l+1, r)$ 的统计结果为 $(open, close)$，则答案为：

$$ \text{answer} = 2 \times (open + close) $$

这一步是整道题的建模核心。
问题至此被转化为：如何动态维护括号序列，并支持区间 $(open, close)$ 查询。

区间 $(open, close)$ 在动态插入下的维护方式

单个括号本身就是一个最小区间：

'(' 对应 $(1,0)$；
')' 对应 $(0,1)$。

当相邻区间合并时，唯一可能产生的新匹配是：

左区间剩余的 '('；
与右区间剩余的 ')'。

因此合并规则固定为：

$$ t = \min(open_L,, close_R) $$

$$ \begin{aligned} open &= open_L + open_R - t, \\ close &= close_L + close_R - t. \end{aligned} $$

一次插入操作，本质上只是向序列中插入新的最小区间 $(1,0)$ 或 $(0,1)$，
原有区间内部的匹配关系不会被破坏，只需在插入位置附近按上述规则重新合并区间信息。

3. 为什么需要平衡树，以及为什么选择 Splay

经过建模后，问题转化为：

动态维护一个序列，支持：

任意位置插入元素；

任意区间 $(open, close)$ 查询。

朴素与线段树方案的不足

数组或字符串模拟，中间插入为 $O(n)$，总复杂度 $O(n^2)$；
普通线段树依赖静态下标，无法处理动态插入。

因此需要一种支持动态序列维护的数据结构。

为什么选择隐式 Splay？

隐式 Splay 具备以下特性：

中序遍历顺序即为序列顺序；
通过子树大小隐式表示下标；
可以在节点中维护区间 $(open, close)$；
均摊时间复杂度为 $O(\log n)$。

区间信息如何挂在树上？

在这种序列型树结构中：

每个节点维护的是“以自身为根的一段连续区间”的统计信息；
左子树、当前节点、右子树分别对应三段连续区间；
节点的 $(open, close)$ 由这三部分按合并规则得到。

当插入新节点或树结构调整时，只需在受影响节点处重新计算区间信息，即可保证整体正确性。

4. Splay 树的基本性质（简述）

Splay 树是一种自调整二叉搜索树，通过访问后的一系列旋转操作，将常访问的节点逐渐拉近根节点。

隐式 Splay 不存储显式 key，而是通过子树大小隐式表示序列下标，因此非常适合处理“第 $k$ 个位置”“区间查询”等操作。

5. 实现思路与代码结构

整体实现可以自然分为三层：

括号段信息 $(open, close)$ 的定义与合并；
隐式 Splay 的通用实现（维护 size 与区间信息）；
题目逻辑：查询区间 $(l+1, r)$，计算答案并插入新括号。

单点与区间信息

$$ \text{info}(c)= \begin{cases} (1,0), & c='(' \\ (0,1), & c=')' \\ (0,0), & \text{哨兵} \end{cases} $$

区间合并规则同第 2 节所述。

区间查询与插入

通过两次结构调整，将目标区间隔离为一棵子树，其根节点维护的 $(open, close)$ 即为查询结果。

每次插入与查询的均摊复杂度均为 $O(\log n)$。

总体复杂度

总时间复杂度：

$$ O(n \log n) $$

结语

解决问题的第一步，一定不是写出代码，而是：

正确抽象“匹配发生变更”的含义；
找到稳定、可维护的区间结构量；
选择合适的数据结构承载这一结构。

一旦模型建立，剩下只是工程实现问题。