No.2554 MMA文字列2 (Query Version)
レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 17
作問者 :
dyktr_06
/ テスター :
sepa38
InTheBloom
Seed57_cash
ryota2357
タグ : / 解いたユーザー数 17
作問者 :


問題文最終更新日: 2023-11-22 09:42:52
元の問題
リンク問題文
MMA文字列とは、 文字の文字列で、 種類のアルファベットからなり、 文字目と 文字目が一致しているものを指します。
長さが の英大文字のみからなる文字列 が与えられます。
個のクエリが与えられるので、順番に処理してください。
クエリは次の 種類のいずれかです。
1 x c
: の 文字目を に変更する。2 l r
: の連続部分文字列 の連続とは限らない部分列であって、MMA文字列であるものは何通りあるかを求めてください。
なお、取り出した部分列が列として等しい場合でも、選んだ位置の集合が異なれば別の取り出し方として数えます。
制約
- は英大文字のみからなる長さが の文字列
- は英大文字
- は整数
入力
入力は以下の形式で標準入力から与えられる。
query query query
各クエリは以下に示す つの形式のいずれかが与えられる。
出力
のクエリの個数を として、 行出力せよ。
行目では 番目のそのようなクエリに対する答えを出力せよ。
サンプル
サンプル1
入力
9 CIRCLEMMA 4 2 1 9 1 8 D 2 1 9 2 2 9
出力
6 5 0
番目のクエリについて、 の連続部分列 CIRCLEMMA
の連続するとは限らない部分列であって、MMA文字列であるようなものは以下の 通りです。
- 文字目を取り出した
CCL
- 文字目を取り出した
CCE
- 文字目を取り出した
CCM
- 文字目を取り出した
CCM
- 文字目を取り出した
CCA
- 文字目を取り出した
MMA
番目のクエリについて、 は CIRCLEMDA
となります。
番目のクエリについて、 の連続部分列 CIRCLEMDA
の連続するとは限らない部分列であって、MMA文字列であるようなものは以下の 通りです。
- 文字目を取り出した
CCL
- 文字目を取り出した
CCE
- 文字目を取り出した
CCM
- 文字目を取り出した
CCD
- 文字目を取り出した
CCA
番目のクエリについて、 の連続部分列 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もしくは右上の雲マークをクリックしてアカウントを作成してください。