(問題 9) どこまで同じ文字？ COBOL(Beta)編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
(文字列の一致判定について)
最後に総まとめとして問題を解いてみましょう。Segment Treeなどと組み合わせて一点更新、区間総和を計算できるようにしましょう。
(問題)
長さ N の英大文字列 S が与えられます。Q 個のクエリに対して前から順番に処理してください。i (1 ≦ i ≦ Q) 番目のクエリは以下の通りです。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N Q
S
I_1 C_1
I_2 C_2
...
I_Q C_Q- 1 行目には 2 つの整数 N,Q が与えられます。
- 2 行目には 1 つの文字列 S が与えられます。
- 2 + i (1 ≦ i ≦ Q) 行目には 1 つの整数 I_i と 1 つの英大文字 C_i が与えられます
- 入力は合計で 2 + Q 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを Q 行で出力してください。
i (1 ≦ i ≦ Q) 行目には前から i 番目のクエリの答えを出力してください。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
- 1 ≦ N ≦ 25000
- 1 ≦ Q ≦ 20000
- S は長さ N の英大文字列
- 1 ≦ I_i ≦ N (1 ≦ i ≦ Q)
- C_i は英大文字 (1 ≦ i ≦ Q)
- 入力例1
-
8 5
ABCBCCAC
2 C
4 C
1 C
3 A
2 A
- 出力例1
-
2
3
6
1
2
