問題一覧 > 通常問題

No.1802 Range Score Query for Bracket Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 66
作問者 : NatsubiSoganNatsubiSogan / テスター : ForestedForested penguinmanpenguinman
5 ProblemId : 7244 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-12-16 21:26:21

問題文

左右対称な括弧列 を、以下のいずれかの条件を満たす 空でない 文字列と定義します。

  • ()
  • ある左右対称な括弧列 $s$ が存在し、(, $s$, ) をこの順に連結した文字列

また、(, ) のいずれかからなる文字列 $s$ に対して、スコア を以下のように定義します。

  • 以下の操作を繰り返すことができる回数。
    • $s$ の 連続 部分列であって左右対称な括弧列であるようなもののうち、最長のものを $1$ つ選び、削除する。
  • なお、部分列を取り除く順番に拠らずこの回数が一意に定まることは証明可能である。

(, ) のいずれかからなる長さ $N$ の文字列 $S$ があります。

$S$ に対して $Q$ 個のクエリが与えられるので、順に処理してください。クエリは $2$ 種類あり、入力形式とクエリの内容は以下の通りです。

  • 1 i: $S$ の $i$ 文字目を、(, ) のうち現在とは異なる文字に変更する。
  • 2 l r: $S$ の $l$ 文字目から $r$ 文字目を取り出した部分文字列のスコアを出力する。

入力

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$
  • $N$ は $1 \leq N \leq 2 \times 10^5$ を満たす整数
  • $Q$ は $1 \leq Q \leq 2 \times 10^5$ を満たす整数
  • $S$ は (, ) のいずれかからなる長さ $N$ の文字列
  • 1 i の形式のクエリについて、$i$ は $1 \leq i \leq N$ を満たす整数
  • 2 l r の形式のクエリについて、$l, r$ は $1 \leq l \leq r \leq N$ を満たす整数
  • 2 l r の形式のクエリが $1$ 回以上登場する

出力

2 l r の形式のクエリそれぞれについて、$1$ 行に答えを出力してください。

出力クエリ $1$ つごとに改行してください。

サンプル

サンプル1
入力
5 3
(()))
2 1 4
1 4
2 2 5
出力
1
2
  • $\mathrm{query}_1$ について:$S$ の $1$ 文字目から $4$ 文字目を取り出した部分文字列、すなわち (()) についてのスコアを求めます。これ自体が左右対称な括弧列なので、この値は明らかに $1$ です。
  • $\mathrm{query}_2$ について:$S$ の $4$ 文字目が ) から ( に変更され、$S$ が (()() となります。
  • $\mathrm{query}_3$ について:$S$ の $2$ 文字目から $5$ 文字目を取り出した部分文字列、すなわち ()() についてのスコアを求めます。この値は $2$ となります。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。