[AdditionalFile5692.zip](file://AdditionalFile5692.zip?type=additional_file)

#5692. 「PA 2026」Splatanie nawiasów

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 5 Splatanie nawiasów

两个单词 $s$ 和 $t$ 的交织（shuffle）是指通过混合 $s$ 和 $t$ 的字母所形成的任意单词。换句话说，交织后的字符串中的每个字母可以染成两种颜色之一，使得读取其中一种颜色的字母序列恰好得到字符串 $s$，而读取另一种颜色的字母序列恰好得到字符串 $t$。

一个由左括号 ( 和右括号 ) 组成的单词 $w$ 被称为合法括号序列，当且仅当 $w$ 中左括号的数量等于右括号的数量，且 $w$ 的任何前缀中左括号的数量都不小于右括号的数量。

给定两个由括号组成的单词 $s$ 和 $t$。计算有多少对 $1 \leq i \leq j \leq |t|$，使得字符串 $s$ 与 $t[i \ldots j]$ （即字符串 $t$ 从位置 $i$ 到位置 $j$ 的非空子串）的交织能够构成一个合法括号序列。

输入格式

第一行输入描述字符串 $s$，第二行输入描述字符串 $t$。

每一行都以一个整数 $n$ $(1 \leq n \leq 100000)$ 开始，后跟一个字符 $c$（该字符为 ( 或 ) 之一），接着是 $n$ 个整数 $a_{1}, \ldots, a_{n}$ $(1 \leq a_{i} \leq 1000000)$。以此方式编码的字符串以字符 $c$ 开头，该字符重复 $a_{1}$ 次，随后是另一种类型的括号重复 $a_{2}$ 次，接着字符 $c$ 再重复 $a_{3}$ 次，以此类推。

输出格式

输出一个整数，表示满足以下条件的对 $(i, j)$ 的数量：字符串 $s$ 和 $t[i \ldots j]$ 的某种交织是一个合法括号序列。

样例 1

输入

3 ( 1 3 1
3 ) 1 3 2

输出

3

此样例中描述的字符串分别是 ()))( 和 )((()))。从第二个字符串中，我们可以取子串 )((() 或 ((() 或 ((。

在第一种情况下，字符串 ()))( 和子串 )((() 的合法交织为 ()((( )))( )。

样例 2

输入

2 ( 1 1
4 ) 2 1 1 2

输出

4

此样例中描述的字符串分别是 () 和 ))()((。请注意，尽管从第二个字符串中截取的第 $2$ 到第 $3$ 个字符的子串与第 $4$ 到第 $5$ 个字符的子串相同，均为 )(，但我们仍将它们视为两次不同的情况进行计数。尽管字符串 () 本身是一个合法括号序列，但我们不计算第二个字符串的空子串。