← 返回题目列表

AtCoder · code_festival_exhibition_b

B. 酷

中文机器翻译题面 查看原题

問題文

高桥很“酷”。开括号(和右括号 我喜欢在仅由)组成的字符串中插入和删除新的括号。 此外,每个字符串都有一个定义值,称为“uncoolness”。一些字符串 为了使 S “完美”而应删除的最小字符数是“不酷”。 如果括号中没有矛盾,则称字符串是“完美的”。特别是0个字符的字符串也是“完美”的。

例如 字符串 ()()(())是“perfect”,“uncool”是 如果删除最后一个括号, 0 。 ())将变为“完美”。因此,“不酷”是 1 。

高桥君是一个字符串 我从朋友那里收到了 S 。现在,我们将在此字符串中插入和删除左括号和右括号。 高桥有时会担心当前的一些字符串“不够酷”。 当高桥君问起“不酷”的时候,请提出这个问题。


入力

输入是从标准输入按以下格式给出的

Q
S
x_1 y_1 z_1
x_2 y_2 z_2
:
x_Q y_Q z_Q
  • 1 第一行显示高桥执行的操作(包括问题)的数量。 Q (1 ≦ Q ≦ 10^5) 被给予。
  • 2 高桥收到的字符串位于第一行。 来自行 S (1 ≦ | S | ≦ 10^5) 被给予。
  • 3 从线 Q 行数过多 i 在线 i 代表操作内容的字符 x_i 和数字 y_i, z_i 用空格分隔。
  • x_i是 在(表示插入左括号的操作。 此操作在第y_i位置插入左括号。此时z_i始终0。
  • x_i是 在)表示插入右括号的操作。 此操作在y_i处插入右括号。此时z_i始终0。
  • x_i是 在D表示删除操作。 这是删除第y_i个字符串的操作。此时z_i始终0。
  • x_i是 在Q表示提问操作。 从第y_i起z_i问题是关于两者之间(包括结尾)的字符串的“不酷”。
  • 没有删除不存在位置的字符、提问或在不存在位置插入字符等输入。此外,所有给出的位置都是 1 索引的。

出力

输出由多行组成。 高桥君每次提问时,都将答案输出一行。


入力例1

5
(()
D 1 0
( 3 0
Q 1 2
) 1 0
Q 2 4

出力例1

0
1

1 第二次操作后的状态是 ()

2 第二次操作后的状态是 ())

3 第二次操作中询问的范围内的字符串是 ()

4 第二次操作后的状态是 (())

5 第二次操作中询问的范围内的字符串是 ())


入力例2

11
(()()(()
( 1 0
( 1 0
D 4 0
Q 2 6
) 5 0
D 8 0
Q 1 9
( 3 0
) 8 0
D 10 0
Q 5 10

出力例2

1
1
4

1 第二次操作后的状态是 ((()()(()

2 第二次操作后的状态是 (((()()(()

3 第二次操作后的状态是 ((()()(()

4 第二次操作中询问的范围内的字符串是 (()()

5 第二次操作后的状态是 ((())()(()

6 第二次操作后的状态是 ((())()()

7 第二次操作中询问的范围内的字符串是 ((())()()

8 第二次操作后的状态是 (((())()()

9 第二次操作后的状态是 (((())())()

10 第二次操作后的状态是 (((())()))

11 第二次操作中询问的范围内的字符串是 ))()))