{"problem":{"name":"「SiR-1」Bracket","description":{"content":"Mirika 有一个长度为 $n$ 的括号序列 $s$。 对于一个括号序列 $S$，Mirika 可以执行两种操作： - 变换：选择一个位置 $i$ 满足 $1 \\leq i \\leq \\lvert S \\rvert$，使得 $S$ 变为 $S_iS_{i+1}\\cdots S_{\\lvert S\\rvert}S_1S_2\\cdots S_{i-2}S_{i-1}$。 - 插入：在这个序列的 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9356"},"statements":[{"statement_type":"Markdown","content":"Mirika 有一个长度为 $n$ 的括号序列 $s$。\n\n对于一个括号序列 $S$，Mirika 可以执行两种操作：\n\n- 变换：选择一个位置 $i$ 满足 $1 \\leq i \\leq \\lvert S \\rvert$，使得 $S$ 变为 $S_iS_{i+1}\\cdots S_{\\lvert S\\rvert}S_1S_2\\cdots S_{i-2}S_{i-1}$。\n- 插入：在这个序列的 **任意位置** 插入一个括号（左右括号均可）。\n\nMirika 定义括号序列 $S$ 的权值 $f(S)$ 为能将这个括号序列变成一个合法括号序列所需的最小操作数。\n\n其中，合法括号序列的定义为：\n\n+ 空串为 合法括号序列。\n+ 若 $\\texttt A$ 为 合法括号序列，则 $\\texttt{(A)}$ 为 合法括号序列。\n+ 若 $\\texttt A, \\texttt B$ 均为 合法括号序列，则 $\\texttt{AB}$ 也为 合法括号序列。\n\n现在 Mirika 想要求出：\n\n$\\sum_{l=1}^n \\sum_{r=l}^n f(s[l,r])$\n\n其中 $s[l,r]$ 表示由 $s_l,s_{l+1},\\cdots,s_r$ 形成的连续子序列。\n\n但是 Mirika 太菜了不会算，于是只好求助于你。\n\n## Input\n\n**本题每个测试点内有多组数据。**\n\n第一行一个正整数 $T$ 表示测试数据组数。\n\n对于每组数据，第一行一个正整数 $n$。\n\n第二行一个长度为 $n$ 的括号序列 $s$。\n\n## Output\n\n输出共 $T$ 行，第 $i$ 行一个整数表示第 $i$ 组测试数据的答案。\n\n[samples]\n\n## Background\n\n> Everything that kills me makes me feel alive.\n\n## Note\n\n### 样例解释\n\n对于 $s = \\texttt{())(}$：\n\n+ 考虑 $s[1,4]=\\texttt{())(}$。执行变换操作 $i=4$，有 $\\texttt{())(} \\Rightarrow \\texttt{(())}$，其中 $\\texttt{(())}$ 是合法括号序列，故 $f(s[1, 4]) = 1$。可以证明不存在更优的策略。\n+ 考虑 $s[2,4]=\\texttt{))(}$。执行变换操作 $i=2$，再在序列开头插入一个左括号，有 $\\texttt{))(} \\Rightarrow \\texttt{)()} \\Rightarrow \\texttt{()()}$，其中 $\\texttt{()()}$ 是合法括号序列，故 $f(s[2, 4]) = 2$。可以证明不存在更优的策略。\n\n### 数据规模与约定\n\n**本题采用捆绑测试。**\n\n+ Subtask 0（15 pts）：$n \\leq 400$，$\\sum n \\leq 800$。\n+ Subtask 1（20 pts）：$n \\leq 2\\times 10^3$，$\\sum n \\leq 4\\times 10^3$。\n+ Subtask 2（5 pts）：$s$ 内不含有右括号。\n+ Subtask 3（10 pts）：对于所有整数 $1\\le i < n$，有 $s_i \\neq s_{i+1}$。\n+ Subtask 4（30 pts）：$n \\leq 2\\times 10^5$，$\\sum n \\leq 5\\times 10^5$。\n+ Subtask 5（20 pts）：无特殊限制。\n\n对于所有数据，$1 \\leq T \\leq 10000$，$1 \\leq n \\leq 2 \\times 10^6$，$1 \\leq \\sum n \\leq 2 \\times 10^7$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9356","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["5\n2\n((\n4\n())(\n5\n()(()\n5\n()()(\n15\n()())(())))()()","4\n11\n16\n12\n241"]],"created_at":"2026-03-03 11:09:25"}}