{"problem":{"name":"C. Bracket Sequences Concatenation Problem","description":{"content":"A bracket sequence is a string containing only characters \"(\" and \")\". A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting chara","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF990C"},"statements":[{"statement_type":"Markdown","content":"A bracket sequence is a string containing only characters \"(\" and \")\".\n\nA regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters \"1\" and \"+\" between the original characters of the sequence. For example, bracket sequences \"()()\", \"(())\" are regular (the resulting expressions are: \"(1)+(1)\", \"((1+1)+1)\"), and \")(\" and \"(\" are not.\n\nYou are given $n$ bracket sequences $s_1, s_2, \\dots , s_n$. Calculate the number of pairs $i, j \\, (1 \\le i, j \\le n)$ such that the bracket sequence $s_i + s_j$ is a regular bracket sequence. Operation $+$ means concatenation i.e. \"()(\" + \")()\" = \"()()()\".\n\nIf $s_i + s_j$ and $s_j + s_i$ are regular bracket sequences and $i \\ne j$, then both pairs $(i, j)$ and $(j, i)$ must be counted in the answer. Also, if $s_i + s_i$ is a regular bracket sequence, the pair $(i, i)$ must be counted in the answer.\n\n## Input\n\nThe first line contains one integer $n \\, (1 \\le n \\le 3 \\cdot 10^5)$ — the number of bracket sequences. The following $n$ lines contain bracket sequences — **non-empty** strings consisting only of characters \"(\" and \")\". The sum of lengths of all bracket sequences does not exceed $3 \\cdot 10^5$.\n\n## Output\n\nIn the single line print a single integer — the number of pairs $i, j \\, (1 \\le i, j \\le n)$ such that the bracket sequence $s_i + s_j$ is a regular bracket sequence.\n\n[samples]\n\n## Note\n\nIn the first example, suitable pairs are $(3, 1)$ and $(2, 2)$.\n\nIn the second example, any pair is suitable, namely $(1, 1), (1, 2), (2, 1), (2, 2)$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"括号序列是仅包含字符 \"(\" 和 \")\" 的字符串。\n\n正则括号序列是指可以通过在原序列的字符之间插入字符 \"1\" 和 \"+\" 转换为正确算术表达式的括号序列。例如，括号序列 \"()()\"、\"(())\" 是正则的（对应的表达式为：\"(1)+(1)\"、\"((1+1)+1)\"），而 \")(\" 和 \"(\" 不是。\n\n给定 $n$ 个括号序列 $s_1, s_2, dots.h, s_n$。计算满足 $s_i + s_j$ 是正则括号序列的对数 $i, j thin (1 lt.eq i, j lt.eq n)$。操作 $+$ 表示拼接，例如 \"()(\" + \")()\" = \"()()()\"。\n\n如果 $s_i + s_j$ 和 $s_j + s_i$ 都是正则括号序列且 $i != j$，则两个对 $(i, j)$ 和 $(j, i)$ 都必须计入答案。此外，如果 $s_i + s_i$ 是正则括号序列，则对 $(i, i)$ 也必须计入答案。\n\n第一行包含一个整数 $n thin (1 lt.eq n lt.eq 3 dot.op 10^5)$ —— 括号序列的数量。接下来的 $n$ 行包含括号序列——由字符 \"(\" 和 \")\" 组成的*非空*字符串。所有括号序列的长度总和不超过 $3 dot.op 10^5$。\n\n在单行中输出一个整数——满足 $s_i + s_j$ 是正则括号序列的对数 $i, j thin (1 lt.eq i, j lt.eq n)$。 \n\n在第一个例子中，合适的对是 $(3, 1)$ 和 $(2, 2)$。\n\n在第二个例子中，任何对都合适，即 $(1, 1), (1, 2), (2, 1), (2, 2)$。\n\n## Input\n\n第一行包含一个整数 $n thin (1 lt.eq n lt.eq 3 dot.op 10^5)$ —— 括号序列的数量。接下来的 $n$ 行包含括号序列——由字符 \"(\" 和 \")\" 组成的*非空*字符串。所有括号序列的长度总和不超过 $3 dot.op 10^5$。\n\n## Output\n\n在单行中输出一个整数——满足 $s_i + s_j$ 是正则括号序列的对数 $i, j thin (1 lt.eq i, j lt.eq n)$。\n\n[samples]\n\n## Note\n\n在第一个例子中，合适的对是 $(3, 1)$ 和 $(2, 2)$。在第二个例子中，任何对都合适，即 $(1, 1), (1, 2), (2, 1), (2, 2)$。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ s_1, s_2, \\dots, s_n $ be $ n $ bracket sequences over the alphabet $ \\{ (, ) \\} $.\n\nFor a bracket sequence $ s $, define:\n- $ \\text{balance}(s) $: the difference between the number of opening and closing parentheses in $ s $, i.e., $ \\text{balance}(s) = (\\# \\text{ of } '(') - (\\# \\text{ of } ')') $.\n- $ \\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 $.\n\nA bracket sequence $ s $ is **valid** (i.e., can be part of a regular bracket sequence when concatenated appropriately) if and only if:\n- $ \\text{min\\_prefix}(s) \\ge 0 $, and\n- $ \\text{balance}(s) \\ge 0 $.\n\nHowever, for concatenation $ s_i + s_j $ to be a **regular bracket sequence**, the following must hold:\n1. $ \\text{balance}(s_i) + \\text{balance}(s_j) = 0 $,\n2. $ \\text{min\\_prefix}(s_i) \\ge 0 $,\n3. $ \\text{min\\_prefix}(s_j) + \\text{balance}(s_i) \\ge 0 $.\n\nLet $ \\mathcal{S} $ be the multiset of the $ n $ sequences.\n\nDefine for each sequence $ s $, its **signature** as the pair:\n$$\n(\\text{balance}(s), \\text{min\\_prefix}(s))\n$$\n\nLet $ f(b, m) $ be the number of sequences $ s $ with $ \\text{balance}(s) = b $ and $ \\text{min\\_prefix}(s) = m $.\n\nThen, the number of valid pairs $ (i, j) $ such that $ s_i + s_j $ is a regular bracket sequence is:\n$$\n\\sum_{b \\in \\mathbb{Z}} \\sum_{m_i \\ge 0} \\sum_{m_j \\ge -b} f(b, m_i) \\cdot f(-b, m_j)\n$$\nwhere the inner sums are over all $ m_i, m_j $ such that:\n- $ m_i \\ge 0 $ (so $ s_i $ has non-negative prefix minima),\n- $ m_j \\ge -b $ (so $ s_j $, when appended after $ s_i $, never drops below zero).\n\nNote: 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).\n\nThus, the total count is:\n$$\n\\boxed{\n\\sum_{b = -\\infty}^{\\infty} \n\\left( \\sum_{\\substack{m_i \\ge 0}} f(b, m_i) \\right) \n\\cdot \n\\left( \\sum_{\\substack{m_j \\ge -b}} f(-b, m_j) \\right)\n}\n$$\n\nIn 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).","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF990C","tags":["implementation"],"sample_group":[["3\n)\n()\n(","2"],["2\n()\n()","4"]],"created_at":"2026-03-03 11:00:39"}}