Codeforces Round #529 (Div. 3)E. Almost Regular Bracket Sequence

問題概要

'(' と ')' で構成された長さ $n$ の文字列 $s$ が与えられる. この文字列のちょうど一文字を変更することで, $s$ が正しい括弧列になるような index は何個あるか？

https://codeforces.com/contest/1095/problem/E

制約

$1 \le n \le 10^6$

解法

正しい括弧列の判定方法は stack を用いた方法がありますが, 次のような条件を満たすときも文字列が正しい括弧列だということができます.

'(' を $1$ に, ')' を $-1$ に置き換えた数列 $a_i$ を考える.
$a_i$ について, その累積和を取ると, すべての要素が $0$ 以上であり, かつ $a_i$ の総和が $0$

総和が $0$ の条件は '(' と ')' の数が等しいことに対応し, 累積和が正だと対応するあまってしまう ')' が存在しないことになります.

これを用いて問題を考えます. まず '(' の数と ')' の数の差が $2$ でないとどうやってもちょうど一つ変更して正しい括弧列にはなりません. その場合は除外して考えます.

'(' が ')' より $2$ つ多い場合を考えましょう. 前述の累積和の配列を $p$ とすれば, $i$ 番目の '(' を ')' に変更することは, $p_i$ 以降すべてに $-2$ を足すことに対応します( $+1$ されていたものが $-1$ されるので). この操作によって総和が $0$ になることは保証されているので, $p_0 \sim p_{i-1}$ までと $p_i \sim p_{n-1}$ までが操作後すべて正であればよいです. これは区間最小値を求めることに対応します. SegmentTree を用いると簡単ですが, 端からの最小値を求められればいいので累積最小値でも求めることができます.