CF1970A3.Balanced Unshuffle (Hard)

本题与中等版本的唯一区别在于输入的最大长度。

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

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

括号序列的平衡度定义为左括号 “(” 的数量减去右括号 “)” 的数量。例如，序列 “(()((” 的平衡度为 $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 1\ 8\ 4\ 2\ 7\ 5\ 3\ 6 \\ \text{字符} &\quad ( ) ( ( ) ( ) ) \end{aligned}$$

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

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

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

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

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

由 ChatGPT 4.1 翻译