P15994 [PA 2026] 归并括号序列 / Splatanie nawiasów

$\large{\bf{{警告：滥用本题评测，一次即可封号。}}}$

我们将字符串 $s$ 与 $t$ 的**归并**定义为通过交错排列 $s$ 与 $t$ 各字符所得到的任意字符串。换言之，归并后的字符可以用两种颜色着色，使得仅读某一种颜色的字符时恰好得到字符串 $s$，仅读另一种颜色的字符时恰好得到字符串 $t$。 由左括号 $\texttt{(}$ 和右括号 $\texttt{)}$ 组成的字符串 $w$ 称为**合法括号表达式**，若 $w$ 中左括号的数量等于右括号的数量，且 $w$ 的每个前缀中左括号的数量不少于右括号的数量。 给定两个由括号组成的字符串 $s$ 和 $t$。计算有多少对 $1 \le i \le j \le |t|$ 满足：存在一个合法括号表达式 $w$，使得 $w$ 是字符串 $s$ 与字符串 $t[i \dots j]$（即 $t$ 从第 $i$ 位到第 $j$ 位的非空子串）的归并。

输入的第一行是字符串 $s$，第二行是字符串 $t$。 为了避免输入过大，我们用如下方式输入字符串： 每行以一个整数 $n$（$1 \le n \le 100\ 000$）开头，紧接一个字符 $c$（为括号 $\texttt{(}$ 或 $\texttt{)}$ 之一），然后是 $n$ 个整数构成的序列 $a_1, \dots, a_n$（$1 \le a_i \le 1\ 000\ 000$）。如此编码的字符串以字符 $c$ 重复 $a_1$ 次开始，其后是另一种括号重复 $a_2$ 次，再是字符 $c$ 重复 $a_3$ 次，依此类推。

输出一个整数——满足条件的对 $(i, j)$ 的数量，即使得字符串 $s$ 与子串 $t[i \dots j]$ 的某个归并为合法括号表达式的对数。

**样例 1 解释**：本样例所描述的字符串为 $\texttt{()))(}$ 和 $\texttt{)((()))}$。从第二个字符串中可取子串 $\texttt{)((()}$、$\texttt{((()))}$ 或 $\texttt{(()}$。 第一种情况下，字符串 $\colorbox{DDDDDD}{\texttt{()))(}}$ 与子串 $\colorbox{BBBBBB}{\texttt{)((()}}$ 的一个合法归并为 $\colorbox{DDDDDD}{\texttt{(}}\colorbox{BBBBBB}{\texttt{)(((}}\colorbox{DDDDDD}{\texttt{)))(}}\colorbox{BBBBBB}{\texttt{)}}$。 **样例 2 解释**：本样例所描述的字符串为 $\texttt{()}$ 和 $\texttt{))()((}$。注意，尽管从第二个字符到第三个字符与从第四个字符到第五个字符给出的是同一个子串 $\texttt{)(}$，我们仍将其计为两次。尽管词 $\texttt{()}$ 本身就是合法括号表达式，空子串不计入统计。