C. Bracket Sequences Concatenation Problem

括号序列是仅包含字符 "(" 和 ")" 的字符串。 正则括号序列是指可以通过在原序列的字符之间插入字符 "1" 和 "+" 转换为正确算术表达式的括号序列。例如，括号序列 "()()"、"(())" 是正则的（对应的表达式为："(1)+(1)"、"((1+1)+1)"），而 ")(" 和 "(" 不是。 给定 $n$ 个括号序列 $s_1, s_2, dots.h, s_n$。计算满足 $s_i + s_j$ 是正则括号序列的对数 $i, j thin (1 lt.eq i, j lt.eq n)$。操作 $+$ 表示拼接，例如 "()(" + ")()" = "()()()"。 如果 $s_i + s_j$ 和 $s_j + s_i$ 都是正则括号序列且 $i != j$，则两个对 $(i, j)$ 和 $(j, i)$ 都必须计入答案。此外，如果 $s_i + s_i$ 是正则括号序列，则对 $(i, i)$ 也必须计入答案。 第一行包含一个整数 $n thin (1 lt.eq n lt.eq 3 dot.op 10^5)$ —— 括号序列的数量。接下来的 $n$ 行包含括号序列——由字符 "(" 和 ")" 组成的*非空*字符串。所有括号序列的长度总和不超过 $3 dot.op 10^5$。 在单行中输出一个整数——满足 $s_i + s_j$ 是正则括号序列的对数 $i, j thin (1 lt.eq i, j lt.eq n)$。 在第一个例子中，合适的对是 $(3, 1)$ 和 $(2, 2)$。 在第二个例子中，任何对都合适，即 $(1, 1), (1, 2), (2, 1), (2, 2)$。 ## Input 第一行包含一个整数 $n thin (1 lt.eq n lt.eq 3 dot.op 10^5)$ —— 括号序列的数量。接下来的 $n$ 行包含括号序列——由字符 "(" 和 ")" 组成的*非空*字符串。所有括号序列的长度总和不超过 $3 dot.op 10^5$。 ## Output 在单行中输出一个整数——满足 $s_i + s_j$ 是正则括号序列的对数 $i, j thin (1 lt.eq i, j lt.eq n)$。 [samples] ## Note 在第一个例子中，合适的对是 $(3, 1)$ 和 $(2, 2)$。在第二个例子中，任何对都合适，即 $(1, 1), (1, 2), (2, 1), (2, 2)$。

Let $ s_1, s_2, \dots, s_n $ be $ n $ bracket sequences over the alphabet $ \{ (, ) \} $. For a bracket sequence $ s $, define: - $ \text{balance}(s) $: the difference between the number of opening and closing parentheses in $ s $, i.e., $ \text{balance}(s) = (\# \text{ of } '(') - (\# \text{ of } ')') $. - $ \text{min\_prefix}(s) $: the minimum prefix sum of balances when scanning $ s $ from left to right, starting at 0. Formally, if $ s = c_1 c_2 \dots c_k $, then define $ p_0 = 0 $, $ p_i = p_{i-1} + 1 $ if $ c_i = '(' $, and $ p_i = p_{i-1} - 1 $ if $ c_i = ')' $; then $ \text{min\_prefix}(s) = \min_{0 \le i \le k} p_i $. A bracket sequence $ s $ is **valid** (i.e., can be part of a regular bracket sequence when concatenated appropriately) if and only if: - $ \text{min\_prefix}(s) \ge 0 $, and - $ \text{balance}(s) \ge 0 $. However, for concatenation $ s_i + s_j $ to be a **regular bracket sequence**, the following must hold: 1. $ \text{balance}(s_i) + \text{balance}(s_j) = 0 $, 2. $ \text{min\_prefix}(s_i) \ge 0 $, 3. $ \text{min\_prefix}(s_j) + \text{balance}(s_i) \ge 0 $. Let $ \mathcal{S} $ be the multiset of the $ n $ sequences. Define for each sequence $ s $, its **signature** as the pair: $$ (\text{balance}(s), \text{min\_prefix}(s)) $$ Let $ f(b, m) $ be the number of sequences $ s $ with $ \text{balance}(s) = b $ and $ \text{min\_prefix}(s) = m $. Then, the number of valid pairs $ (i, j) $ such that $ s_i + s_j $ is a regular bracket sequence is: $$ \sum_{b \in \mathbb{Z}} \sum_{m_i \ge 0} \sum_{m_j \ge -b} f(b, m_i) \cdot f(-b, m_j) $$ where the inner sums are over all $ m_i, m_j $ such that: - $ m_i \ge 0 $ (so $ s_i $ has non-negative prefix minima), - $ m_j \ge -b $ (so $ s_j $, when appended after $ s_i $, never drops below zero). Note: For $ s_i + s_j $ to be regular, $ s_i $ must never go negative (condition 2), and $ s_j $ must not cause the total prefix to go negative after absorbing the balance of $ s_i $ (condition 3). The total balance must be zero (condition 1). Thus, the total count is: $$ \boxed{ \sum_{b = -\infty}^{\infty} \left( \sum_{\substack{m_i \ge 0}} f(b, m_i) \right) \cdot \left( \sum_{\substack{m_j \ge -b}} f(-b, m_j) \right) } $$ In practice, $ b $ ranges only over integers that appear as balances in the input, and $ m_i, m_j $ are bounded by the maximum absolute prefix deviation in the input (which is $ \le 3 \cdot 10^5 $ in total length).