注意

入力例 1 に関する説明に誤りがあります。

• 2 回目の操作が終わったあとの状態は ()(
• 4 回目の操作が終わったあとの状態は )()((
• 5 回目の操作が終わったあとの状態は ()(

解法

ついでに少し触れます。

カッコ列から、正しいカッコ対を最大限取り去ると、)))))((( のように「閉じ括弧 \(x\) 個 → 開き括弧 \(y\) 個」という文字列が残ります。カッコ悪さは \(x+y\) です。

カッコ列 \(S\) に対してこの \((x, y)\) を \(f(S)\) と書けば、\(f(S+T)\) は \(f(S), f(T)\) から計算できることが分かります。したがって、例えば追加・削除がなければ解答クエリにはセグメント木・平方分割といった手法で答えることができます。

あとは、追加・削除ができるようにすればよいです。

• 二分木に適宜回転して、平衡性を持たせる（平衡二分木）
• 平方分割で列をバケットに分けて持ち、あるバケットが満杯になるたびに作り直す

などの方法があると思います。