問題
思考過程
最初の方針（遅延セグ木解法）
対応するカッコがちゃんと閉じているか判定する問題。この手の問題ですぐに思いつくのは、"(" なら +1して ")" なら-1していく数列を作り、「範囲の両端で同じ値」かつ「間の数字が両端の数字を下回らない」を満たしているかチェックすること。
問題は、2箇所の文字を入れ替えた時の処理。数列の値がどうなるかに着目すると、"(" が ")" になると以降の値が-2、逆だと+2になる。範囲の値が変化するのが対応できるのは遅延セグ木が考えられる。
なので、元の数列から入れ替わりがあった範囲で±2することで変化量を反映し、変化後の値を見ていけば良さそう。「範囲の両端で同じ値」は簡単にでき、「間の数字が両端の数字を下回らない」も「ある範囲の最小値」と「両端の数字」をもとめて、変化量を比べればできそうに見える。
しかし、この方針だとだめで、「ある範囲」での変化量は一定でない可能性があるため、変化後の最小値がセグ木を利用して求められない。例えば、(1, N), (2, N), ..., (N - 1, N)で入れ替えた場合、変化量が各区間で異なる変化量になる。
ということで、別の方針を考える。
組み合わせの更新解法
対応付けされる括弧を管理して、入れ替え時に対応する括弧を更新していく方針を考える。先に結論をいうと、これもダメだった。
上記の方針でうまいくためには、「入れ替え時に関係する括弧だけを組み替えたとき、それに関与しない箇所は対応が変わらない」という仮定が必要になるが、これが成り立たない。
例えば、「((()()))」で1, 4番目の括弧を入れ替えると「)(((()))」となるが、舌の図でいう緑で囲った位置の括弧が、入れ替え位置と関係ない場所にも関わらず対応する括弧が変化してしまっている。
ということで、この方針でもダメということになる。
解説を見る
流石に手詰まりになったので解説を見たが、実はセグ木でもいけるし、遅延セグ木でよかったということがわかる……。ただ、セグ木への乗せ方はあんまり自明じゃないような気がして、理解するまでに結構かかってしまった。
最初の方針で作った数列をもとに、「区間での和」と「その区間中で、左から足し算していった時にできる値の最小値」の2つを記録させていくことにする。つまり、各要素は "("なら (1, 0), ")"なら (-1, -1)として乗せる（解説とは要素が逆にしている）。
問題は区間を合わせるときにどう演算するかである。例えば 「()」の場合、左の要素が(1, 0)で右の要素が(-1, -1)のとき、(0, 0)としたい。「区間での和」は単純に足し算すればいいので簡単。もう一方の方の「最小値」の更新方法をどうするかについてだが、こちらは単純に両方の要素の最小値を更新していくだけだとうまくいかない。「左から足し算していった時の最小値」なので、右側の要素については、それまでに左側の要素の合計を足し上げて上げる必要がある。ということで、左の要素をa、右の要素をbとすると、(a[0] + b[0], min(a[1], a[0] + b[1]))となる。
（余談：もともと手元にあったセグ木のコードが演算順序を考慮していない作りになってしまっていたので、その修正が大変だった）
なお、遅延セグ木でも解けるらしい（そっちは後日……）。
