CF1970A2.Balanced Unshuffle (Medium)

本题与其简单版本的区别已用加粗字体标出。

括号序列是仅由字符“(”和“)”组成的字符串，例如“(()((”。

平衡括号序列是指可以通过在括号中插入数字和运算符后成为合法数学表达式的括号序列，例如“(()(()))”。

括号序列的平衡度定义为左括号“(”的数量减去右括号“)”的数量。例如，序列“(()((”的平衡度为 $3$。

平衡括号序列也可以定义为平衡度为 $0$，且其每个前缀的平衡度都不为负数的括号序列。

我们定义“平衡洗牌”操作如下：对于一个括号序列，首先，对于序列中的每个字符，计算该字符之前的前缀的平衡度，并将其与该字符在原序列中的位置一起记录在表格中。例如：

$$\begin{aligned} \text{前缀平衡度} &\quad 0\ 1\ 2\ 1\ 2\ 3\ 2\ 1 \\ \text{位置} &\quad 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8 \\ \text{字符} &\quad ( ( ) ( ( ) ) ) \end{aligned}$$

然后，将该表格的列按照前缀平衡度升序排序，若平衡度相同，则按位置降序排序。以上例为例，排序后得到：

$$\begin{aligned} \text{前缀平衡度} &\quad 0\ 1\ 1\ 1\ 2\ 2\ 2\ 3 \\ \text{位置} &\quad 8\ 7\ 4\ 2\ 5\ 3\ 1\ 6 \\ \text{字符} &\quad ) ) ( ( ( ) ( ) \end{aligned}$$

表格最后一行形成另一个括号序列，在本例中为“()(()())”。这个序列称为对输入序列应用平衡洗牌操作的结果，简称为该序列的平衡洗牌。

令人惊讶的是，任何平衡括号序列的平衡洗牌总是另一个平衡括号序列（证明略）。更令人惊讶的是，两个不同的平衡括号序列的平衡洗牌总是不同的，因此平衡洗牌操作在任意长度的平衡括号序列集合上是一个双射（证明亦略）。

现在给定一个平衡括号序列。请你求出它的原像：即求一个平衡括号序列 $t$，使得 $t$ 的平衡洗牌等于给定序列。

输入仅一行，包含一个仅由“(”和“)”组成的字符串 $s$。保证该字符串是非空的平衡括号序列，且长度不超过 $1000$。

输出一个平衡括号序列 $t$，使得 $t$ 的平衡洗牌等于 $s$。保证答案一定存在且唯一。

由 ChatGPT 4.1 翻译