B - カッコつけ Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は「カッコつけ」です。開きカッコ(と閉じカッコ)だけからなる文字列に、新しくカッコを挿入したり削除したりするのが大好きです。 また、各文字列には「カッコ悪さ」という値が定義されます。ある文字列 S を「完璧」にするために取り除くべき文字の個数の最小値が「カッコ悪さ」です。 カッコ付けの対応に矛盾がなかった場合その文字列は「完璧」であると言います。特に、0文字の文字列も「完璧」です。

例えば ()()(())という文字列は「完璧」で、「カッコ悪さ」は 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-indexedである。

出力

出力は複数行からなる。 高橋君が質問するたびにその答えを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 回目の操作で質問されている範囲の文字列は ))()))