AT_abc350_f [ABC350F] Transpose

题目描述

给定一个由英文字母大小写和 (、) 组成的字符串 $S = S_1 S_2 S_3 \dots S_{|S|}$。
字符串 $S$ 中的括号是配对的。

重复进行如下操作，直到无法继续为止：

• 首先，选择一组满足以下所有条件的整数对 $(l, r)$：
  • $l < r$
  • $S_l = ($
  • $S_r = )$
  • $S_{l+1}, S_{l+2}, \dots, S_{r-1}$ 全部为英文字母（大写或小写）
• 令 $T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}$。
  • 其中，$\overline{x}$ 表示将字符串 $x$ 的大小写反转后的结果。
• 然后，将 $S$ 的第 $l$ 个字符到第 $r$ 个字符删除，并在该位置插入 $T$。

具体操作过程请参见输入输出样例。

通过上述操作，可以将所有的 ( 和 ) 都去除，并且最终得到的字符串与操作的方法和顺序无关，这一点可以得到证明。
请输出最终得到的字符串。

“$S$ 中的括号是配对的”是什么意思？首先，定义“正确的括号序列”如下：

• 空字符串
• 存在某个正确的括号序列 $A$，将 (、$A$、) 按此顺序连接得到的字符串
• 存在某些非空的正确括号序列 $A, B$，将 $A, B$ 按此顺序连接得到的字符串

$S$ 中的括号是配对的，指的是将 $S$ 中的所有 ( 和 ) 按顺序取出后，它们组成的字符串是一个正确的括号序列。

输入格式

输入以以下格式从标准输入读入。

$S$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

((A)y)x

输出 #1

YAx

输入输出样例 #2

输入 #2

((XYZ)n(X(y)Z))

输出 #2

XYZNXYZ

输入输出样例 #3

输入 #3

(((()))(()))(())

输出 #3

输入输出样例 #4

输入 #4

dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve

输出 #4

dFGsdccCrFNNnplCtQPOKjsiIwwEysAve

说明/提示

限制条件

• $1 \leq |S| \leq 5 \times 10^5$
• $S$ 由英文字母大小写和 (、) 组成
• $S$ 中的括号是配对的

样例解释 1

对于 $S=$ ((A)y)x，操作如下：

• 选择 $l=2, r=4$。此时被删除的字符串为 (A)，插入 a。
• 操作后，$S=$ (ay)x。
• 选择 $l=1, r=4$。此时被删除的字符串为 (ay)，插入 YA。
• 操作后，$S=$ YAx。 括号全部去除后，字符串为 YAx，请输出该字符串。

样例解释 2

对于 $S=$ ((XYZ)n(X(y)Z))，操作如下：

• 选择 $l=10, r=12$。此时被删除的字符串为 (y)，插入 Y。
• 操作后，$S=$ ((XYZ)n(XYZ))。
• 选择 $l=2, r=6$。此时被删除的字符串为 (XYZ)，插入 zyx。
• 操作后，$S=$ (zyxn(XYZ))。
• 选择 $l=6, r=10$。此时被删除的字符串为 (XYZ)，插入 zyx。
• 操作后，$S=$ (zyxnzyx)。
• 选择 $l=1, r=9$。此时被删除的字符串为 (zyxnzyx)，插入 XYZNXYZ。
• 操作后，$S=$ XYZNXYZ。 括号全部去除后，字符串为 XYZNXYZ，请输出该字符串。

样例解释 3

操作结果也可能为空字符串。

由 ChatGPT 4.1 翻译