実行時間制限: 2 sec / メモリ制限: 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 回目の操作で質問されている範囲の文字列は ))()))