G: Flipping Parentheses
問題
バランスの取れた括弧文字列が与えられる。
Q個のクエリに答えよ。
クエリは整数q[i]で与えられ、文字列の位置q[i]の括弧の向きをフリップした後、フリップすると文字列全体のバランスを取るような最も左のインデックスを出力し、そこの括弧をフリップする。
解法
自分で実装したのでやや詳しく書く。
バランスが取れているとは、閉括弧が先攻し過ぎていないか・開括弧と閉括弧の数が等しいかということ。
'('を+1、')'を-1と考えると括弧の深さは先頭からの和となる。
sums[k] := sum_{i=0}^{k} s[i]
バランスが取れた括弧文字列の必要十分条件は
forall k, sums[k] >= 0
sums[N-1] = 0
である。
必要な操作は
ある位置iの括弧をフリップするとき、
- s[i] = '('を')'にフリップするとき
(1) for k in [i..N-1] sums[k] -= 2 とする。
(2) フリップすべきインデックスは最も左のs[j] = ')'であるjを求める。
- s[i] = ')'を'('にフリップするとき
(3) for k in [i..N-1] sums[k] += 2 とする。
(4) フリップすべきインデックスは(forall k, j<=k<N, sums[j]>=2)を満たす最も左のjを求める。(このjより左をフリップするとsumsに負の要素ができてしまう)。
これらの操作が全部できれば解ける。
(2)は閉括弧のインデックスをstd::set<int>に記憶し、フリップするたびにinsert、eraseし、beginで最小要素にアクセスできる。
残りはsegment treeで解く。
(update) 区間に加算
(query) 区間の最小値
(1)(3)は(update)でできる。
(4)もsegment treeで計算できるが(query)を二分探索することでlogN余計に掛けてもできる。
つまりquery(j, N)>=2を満たす最小のjを二分探索で発見すれば良い。
実はプログラミングコンテストチャレンジブックには「一要素変更、区間minのRMQ」と「区間加算、区間和のsegment tree」は載っているが上のsegment treeは無い。上のsegment treeは「区間加算、区間和のsegment tree」を少し応用することでできる。segment treeの各頂点にはその対応する区間の最小値とその区間の要素全てに加算される値を持たせる。
このsegment treeは「Starry Sky」という名の問題が出された例があるのでstarry sky木で通じる人もいる。
