103505: [Atcoder]ABC350 F - Transpose

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：7 Solved：0

Description

Score: $550$ points

Problem Statement

You are given a string $S = S_1 S_2 S_3 \dots S_{|S|}$ consisting of uppercase and lowercase English letters, (, and ).
The parentheses in the string $S$ are properly matched.

Repeat the following operation until no more operations can be performed:

  • First, select one pair of integers $(l, r)$ that satisfies all of the following conditions:
    • $l < r$
    • $S_l =$ (
    • $S_r =$ )
    • Each of the characters $S_{l+1}, S_{l+2}, \dots, S_{r-1}$ is an uppercase or lowercase English letter.
  • Let $T = \overline{S_{r-1} S_{r-2} \dots S_{l+1}}$.
    • Here, $\overline{x}$ denotes the string obtained by toggling the case of each character in $x$ (uppercase to lowercase and vice versa).
  • Then, delete the $l$-th through $r$-th characters of $S$ and insert $T$ at the position where the deletion occurred.

Refer to the sample inputs and outputs for clarification.

It can be proved that it is possible to remove all (s and )s from the string using the above operations, and the final string is independent of how and in what order the operations are performed.
Determine the final string.

What does it mean that the parentheses in $S$ are properly matched? First, a correct parenthesis sequence is defined as follows:
  • A correct parenthesis sequence is a string that satisfies one of the following conditions:
    • It is an empty string.
    • There exists a correct parenthesis sequence $A$, and the string is formed by concatenating (, $A$, ) in this order.
    • There exist non-empty correct parenthesis sequences $A$ and $B$, and the string is formed by concatenating $A$ and $B$ in this order.
The parentheses in $S$ are properly matched if and only if the (s and )s extracted from $S$ without changing the order form a correct parenthesis sequence.

Constraints

  • $1 \le |S| \le 5 \times 10^5$
  • $S$ consists of uppercase and lowercase English letters, (, and ).
  • The parentheses in $S$ are properly matched.

Input

The input is given from Standard Input in the following format:

$S$

Output

Print the final string.

Sample Input 1

((A)y)x

Sample Output 1

YAx

Let us perform the operations for $S =$ ((A)y)x.

  • Choose $l=2$ and $r=4$. The substring (A) is removed and replaced with a.
    • After this operation, $S =$ (ay)x.
  • Choose $l=1$ and $r=4$. The substring (ay) is removed and replaced with YA.
    • After this operation, $S =$ YAx.

After removing the parentheses, the string becomes YAx, which should be printed.

Sample Input 2

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

Sample Output 2

XYZNXYZ

Let us perform the operations for $S =$ ((XYZ)n(X(y)Z)).

  • Choose $l=10$ and $r=12$. The substring (y) is removed and replaced with Y.
    • After this operation, $S =$ ((XYZ)n(XYZ)).
  • Choose $l=2$ and $r=6$. The substring (XYZ) is removed and replaced with zyx.
    • After this operation, $S =$ (zyxn(XYZ)).
  • Choose $l=6$ and $r=10$. The substring (XYZ) is removed and replaced with zyx.
    • After this operation, $S =$ (zyxnzyx).
  • Choose $l=1$ and $r=9$. The substring (zyxnzyx) is removed and replaced with XYZNXYZ.
    • After this operation, $S =$ XYZNXYZ.

After removing the parentheses, the string becomes XYZNXYZ, which should be printed.

Sample Input 3

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

Sample Output 3



The final outcome may be an empty string.










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









Sample Output 4
dFGsdccCrFNNnplCtQPOKjsiIwwEysAve



	  

    

  

      

      

          
Input

          

		  


		  

      

    

        

        

          
Output

          
得分：550分





问题描述
你被给定一个字符串 $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$ 中提取的 ( 和 ) 形成一个正确括号序列。











约束
    

  • $1 \le |S| \le 5 \times 10^5$
    • 

  • $S$ 由大写和小写英文字母，( 和 ) 组成。
    • 

  • $S$ 中的括号匹配正确。
    • 













输入
输入通过标准输入给出以下格式：


$S$










输出
打印最终字符串。












样例输入 1
((A)y)x










样例输出 1
YAx



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


    

  • 选择 $l=2$ 和 $r=4$。子字符串 (A) 被移除并替换为 a$。 
      

    • 执行此操作后，$S = (ay)x$。
      • 

    

    • 

  • 选择 $l=1$ 和 $r=4$。子字符串 (ay) 被移除并替换为 YA$。 
      

    • 执行此操作后，$S = YAx$。
      • 

    

    • 



移除括号后，字符串变为 YAx，应打印该字符串。











样例输入 2
((XYZ)n(X(y)Z))










样例输出 2
XYZNXYZ



对于 $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
(((()))(()))(())










样例输出 3


最终结果可能为空字符串。











样例输入 4
dF(qT(plC())NnnfR(GsdccC))PO()KjsiI((ysA)eWW)ve










样例输出 4
dFGsdccCrFNNnplCtQPOKjsiIwwEysAve






        

    

  
                

      

        

        Source/Category        

        
      

    

    

  
    

      

        

        加入题单
        

        


		

		
				算法标签：