CF990C Bracket Sequences Concatenation Problem

括号序列是仅包含字符“(”和“)”的字符串。 一个合法括号序列是指可以通过在原序列的字符之间插入“1”和“+”字符，将其转化为一个正确的算术表达式的括号序列。例如，括号序列“()()”、“(())”是合法的（对应的表达式分别为“(1)+(1)”和“((1+1)+1)”），而“) (”和“(”不是合法的。 给定 $n$ 个括号序列 $s_1, s_2, \dots, s_n$，计算有多少对 $i, j\ (1 \le i, j \le n)$，使得括号序列 $s_i + s_j$ 是一个合法括号序列。这里的 $+$ 表示连接操作，例如“() (” + “) ()” = “()()()”。 如果 $s_i + s_j$ 和 $s_j + s_i$ 都是合法括号序列，且 $i \ne j$，那么 $(i, j)$ 和 $(j, i)$ 都要计入答案。如果 $s_i + s_i$ 是合法括号序列，则 $(i, i)$ 也要计入答案。

第一行包含一个整数 $n\ (1 \le n \le 3 \times 10^5)$，表示括号序列的数量。接下来的 $n$ 行，每行一个括号序列——非空字符串，仅包含字符“(”和“)”。所有括号序列的总长度不超过 $3 \times 10^5$。

输出一个整数，表示满足条件的 $(i, j)\ (1 \le i, j \le n)$ 对数，使得 $s_i + s_j$ 是合法括号序列。

在第一个样例中，满足条件的对为 $(3, 1)$ 和 $(2, 2)$。 在第二个样例中，任意一对都满足条件，即 $(1, 1), (1, 2), (2, 1), (2, 2)$。 由 ChatGPT 4.1 翻译