問題文
高桥很“酷”。开括号(和右括号
我喜欢在仅由)组成的字符串中插入和删除新的括号。
此外,每个字符串都有一个定义值,称为“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 第二次操作中询问的范围内的字符串是 ))()))