問題一覧 > 通常問題

No.2554 MMA文字列2 (Query Version)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 : dyktr_06dyktr_06 / テスター : sepa38sepa38 InTheBloomInTheBloom Seed57_cashSeed57_cash ryota2357ryota2357
1 ProblemId : 10257 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-22 09:42:52

元の問題

リンク

問題文

MMA文字列とは、$3$ 文字の文字列で、$2$ 種類のアルファベットからなり、$1$ 文字目と $2$ 文字目が一致しているものを指します。

長さが $N$ の英大文字のみからなる文字列 $S$ が与えられます。

$Q$ 個のクエリが与えられるので、順番に処理してください。

クエリは次の $2$ 種類のいずれかです。

  • 1 x c: $S$ の $x$ 文字目を $c$ に変更する。
  • 2 l r: $S$ の連続部分文字列 $S_{l} S_{l + 1} … S_r$ の連続とは限らない部分列であって、MMA文字列であるものは何通りあるかを求めてください。

なお、取り出した部分列が列として等しい場合でも、選んだ位置の集合が異なれば別の取り出し方として数えます。

制約

  • $3 \leq N \leq 5 \times 10^{4}$
  • $S$ は英大文字のみからなる長さが $N$ の文字列
  • $1 \leq Q \leq 5 \times 10^{4}$
  • $1 \leq x \leq N$
  • $c$ は英大文字
  • $1 \leq l \leq r \leq N$
  • $N, Q, x, l, r$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ 
$S$ 
$Q$ 
query $1$  
query $2$  
$\vdots$

query $Q$

各クエリは以下に示す $2$ つの形式のいずれかが与えられる。

$1$ $x$ $c$ 

$2$ $l$ $r$

出力

$2$ のクエリの個数を $q$ として、$q$ 行出力せよ。

$j$ $(1 \leq j \leq q)$ 行目では $j$ 番目のそのようなクエリに対する答えを出力せよ。

サンプル

サンプル1
入力
9
CIRCLEMMA
4
2 1 9
1 8 D
2 1 9
2 2 9
出力
6
5
0

$1$ 番目のクエリについて、$S$ の連続部分列 CIRCLEMMA の連続するとは限らない部分列であって、MMA文字列であるようなものは以下の $6$ 通りです。

  • $1, 4, 5$ 文字目を取り出したCCL
  • $1, 4, 6$ 文字目を取り出したCCE
  • $1, 4, 7$ 文字目を取り出したCCM
  • $1, 4, 8$ 文字目を取り出したCCM
  • $1, 4, 9$ 文字目を取り出したCCA
  • $7, 8, 9$ 文字目を取り出したMMA

$2$ 番目のクエリについて、$S$ は CIRCLEMDA となります。

$3$ 番目のクエリについて、$S$ の連続部分列 CIRCLEMDA の連続するとは限らない部分列であって、MMA文字列であるようなものは以下の $5$ 通りです。

  • $1, 4, 5$ 文字目を取り出したCCL
  • $1, 4, 6$ 文字目を取り出したCCE
  • $1, 4, 7$ 文字目を取り出したCCM
  • $1, 4, 8$ 文字目を取り出したCCD
  • $1, 4, 9$ 文字目を取り出したCCA

$4$ 番目のクエリについて、$S$ の連続部分列 IRCLEMDA の連続するとは限らない部分列であって、MMA文字列であるようなものはありません。

サンプル2
入力
24
MMACONTESTISFORBEGINNERS
8
2 1 24
2 1 12
2 10 24
1 9 N
2 1 24
1 13 P
2 2 12
2 9 16
出力
82
12
11
90
5
0

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