猫咪升级（简单版）题解

思路

把每一对匹配括号看成一棵有根有序树中的一个结点。一个结点直接包含的若干对括号就是它的孩子；字符串最外层的若干括号块则是虚根的孩子。

任意 RBS 子串恰好对应同一个父亲的一段连续孩子。若某个结点有 $c$ 个孩子，设每个孩子内部的 RBS 子串数已经求出，则该结点覆盖的字符串内部包含：

• 结点自身对应的一个 RBS；
• 各孩子内部的全部答案；
• 由至少两个连续孩子拼接得到的 $c(c-1)/2$ 个 RBS。

因此

$$f(u)=1+\sum_{v\text{ 是 }u\text{ 的孩子}}f(v)+\frac{c(c-1)}2.$$

小规模可以枚举查询区间中的所有子串并检查括号平衡。中规模可以对每次查询重新用栈建立局部森林，在线计算上述递推，复杂度为区间长度。满分做法只需对整串建树一次。

做法

用栈扫描字符串，为每个左括号建立结点，并在遇到匹配右括号时记录结点编号。按结点编号逆序计算 $f$。

对同一父结点的孩子，按从左到右顺序记录：

• rank(u)：$u$ 是第几个孩子；
• prefix(u)：$u$ 之前所有兄弟的 $f$ 之和。

查询区间 $[l,r]$ 是 RBS，所以 $l$ 对应的左括号结点 $x$ 与 $r$ 对应的右括号结点 $y$ 一定是同一父结点下的一段连续兄弟。设这段共有

$$c=rank(y)-rank(x)+1$$

个结点，则答案为

$$prefix(y)+f(y)-prefix(x)+\frac{c(c-1)}2.$$

第一项求出所有选中兄弟各自内部的答案，第二项补上由多个兄弟拼接形成的 RBS。

复杂度

预处理时间和空间复杂度均为 $O(n)$，每个查询 $O(1)$，总时间复杂度为 $O(n+q)$。