Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 223 F 問題 Parenthesis Checking

AtCoder ABC ABC223 F問題 500 pts

問題

提出解答

問題の概要

$"{\tt (}", "{\tt )}"$ からなる長さ $N$ の文字列 $S$ が与えられる. 以下の $Q$ 個のクエリを順に処理せよ.

$S$ の $l$ 文字目と $r$ 文字目を入れ替える.
$S$ の $l$ 文字目から $r$ 文字目までの部分文字列が正しい文字列かどうかを判定する.

制約

$1 \leq N,Q \leq 2 \times 10^5$
$1 \leq l \leq r \leq N$
$S$ は $"{\tt (}", "{\tt )}"$ からなる長さ $N$ の文字列

解法

$"{\tt (}", "{\tt )}"$ からなる文字列 $T$ において, 以下は同値である.

$T$ は正しい文字列
列をならば, , ならば, とした列とし, 累積和をとしたとき, 以下が成立する.
- $\widetilde{V}_{|T|}=0$
- $\min \widetilde{V} \geq 0$ (※ $\min \widetilde{V}=0$ と同値)

そして, 更新は1点, 取得は区間であることから, 以下のモノイド $M$ を搭載したセグメント木を用いることで高速に処理できる.

$M=\mathbb{Z} \times \widehat{\mathbb{Z}}$ ただし, $\widehat{\mathbb{Z}}:=\mathbb{Z} \cup \{\infty\}$
演算 $\otimes$ は $(a,b) \otimes (a', b'):=(a+a', \min (b,a+b'))$
単位元は $(0,\infty)$

ここで, $(a,b) \in M$ に対して, $a$ は累積和, $b$ は累積和の最小値を表している. そして, $"{\tt (}"$ を $(1,0) \in M$ に, $"{\tt )}"$ を $(-1,-1)$ に対応させることで, 整合性を持たせられる.

計算量は, $O(Q \log N)$ である.