問題一覧 > 通常問題

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文字列とは、33 文字の文字列で、22 種類のアルファベットからなり、11 文字目と 22 文字目が一致しているものを指します。

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

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

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

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

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


制約

  • 3N5×1043 \leq N \leq 5 \times 10^{4}
  • SS は英大文字のみからなる長さが NN の文字列
  • 1Q5×1041 \leq Q \leq 5 \times 10^{4}
  • 1xN1 \leq x \leq N
  • cc は英大文字
  • 1lrN1 \leq l \leq r \leq N
  • N,Q,x,l,rN, Q, x, l, r は整数

入力

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

NN 
SS 
QQ 
query 11  
query 22  
\vdots

query QQ 

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

11 xx cc 
22 ll rr

出力

22 のクエリの個数を qq として、qq 行出力せよ。

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

サンプル

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

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

  • 1,4,51, 4, 5 文字目を取り出したCCL
  • 1,4,61, 4, 6 文字目を取り出したCCE
  • 1,4,71, 4, 7 文字目を取り出したCCM
  • 1,4,81, 4, 8 文字目を取り出したCCM
  • 1,4,91, 4, 9 文字目を取り出したCCA
  • 7,8,97, 8, 9 文字目を取り出したMMA

22 番目のクエリについて、SSCIRCLEMDA となります。

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

  • 1,4,51, 4, 5 文字目を取り出したCCL
  • 1,4,61, 4, 6 文字目を取り出したCCE
  • 1,4,71, 4, 7 文字目を取り出したCCM
  • 1,4,81, 4, 8 文字目を取り出したCCD
  • 1,4,91, 4, 9 文字目を取り出したCCA

44 番目のクエリについて、SS の連続部分列 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もしくは右上の雲マークをクリックしてアカウントを作成してください。