P15730 [JAG 2024 Summer Camp #2] Broken Parentheses

我们定义一个**正确的括号序列**为满足以下任一条件的字符串： - 它是一个空字符串。 - 它由 $($、$A$、$)$ 按此顺序连接而成，其中 $A$ 是一个正确的括号序列。 - 它由 $A$ 和 $B$ 按此顺序连接而成，其中 $A$ 和 $B$ 都是非空的正确括号序列。 给定一个长度为 $N$ 的字符串 $S$，由字符 $($ 和 $)$ 组成。 对于每个满足 $0 \leq i \leq N$ 的 $i$，定义字符串 $T_i$ 为：将 $S$ 的长度为 $N - i$ 的后缀与 $S$ 的长度为 $i$ 的前缀的反转字符串按此顺序连接而得到的字符串。也就是说，如果我们用 $S_i$ 表示 $S$ 的第 $i$ 个字符，那么 $T_i$ 由字符 $S_{i+1}, S_{i+2}, \ldots, S_N, S_i, \ldots, S_2, S_1$ 按顺序排列而成。 对于每个满足 $0 \leq i \leq N$ 的 $T_i$，解决以下问题： - 考虑一种操作：将 $T_i$ 中的一个字符替换为 $($ 或 $)$。求使 $T_i$ 成为一个正确的括号序列所需的最少操作次数。

输入以如下格式给出： $$ \begin{aligned} &N \\ &S \end{aligned} $$ - $2 \leq N \leq 200,000$ - $N$ 是偶数。 - $S$ 是一个长度为 $N$ 的字符串，仅由 $($ 和 $)$ 组成。

输出 $N + 1$ 行。在第 $i + 1$ 行输出 $T_i$ 的答案。

翻译由 DeepSeek V3.2 完成