概要

各更新のたびに「隣り合う2文字が等しい場所の数」を高速に求める問題です。
変更される1文字の周辺だけが影響することを使うと、1回の更新を \(O(1)\) で処理できます。

考察

一致ペアとは、位置 \(i\) について \(S_i = S_{i+1}\) となるものの個数です。

素朴に毎回文字列全体を見て一致ペアを数えると、1回あたり \(O(N)\)、全体で \(O(NQ)\) です。
制約は \(N \le 10^6,\ Q \le 10^5\) なので、これは間に合いません。

ここで重要なのは、1文字だけ変更したとき、影響を受ける一致ペアは最大2か所という点です。

• 変更位置を \(i\)（0-index）とすると、
  • ペア \((i-1, i)\)
  • ペア \((i, i+1)\) のみが変化しうる。 それ以外のペアは、使っている文字が変わらないので状態不変です。

したがって、現在の一致ペア数 same を持っておき、更新のたびにこの2ペア分だけ増減調整すればよいです。

例えば、... A B C ... の中央 B を A に変えるとき：

• 左ペア (A,B) は不一致→一致 なので +1
• 右ペア (B,C) は元の関係に応じて変化

この差分更新で高速に処理できます。

アルゴリズム

1. 初期文字列について、全ての隣接ペアを見て一致数 same を計算する。
2. 各更新 \((i, c)\)（入力は1-indexなので0-indexへ変換）について：
   • 変更前文字を old = S[i] とする。
   • old == c なら何も変わらないので same はそのまま。
   • old != c なら以下を行う：
     • 左隣が存在するなら（i-1 >= 0）
       

          - 変更前に `(i-1,i)` が一致していたら `same -= 1`  
          - 変更後に `(i-1,i)` が一致するなら `same += 1`
       

     • 右隣が存在するなら（i+1 < N）
       

          - 変更前に `(i,i+1)` が一致していたら `same -= 1`  
          - 変更後に `(i,i+1)` が一致するなら `same += 1`
       

     • 最後に S[i] = c に更新。
   • 現在の same を出力に追加。
3. 全更新後、答えをまとめて出力。

計算量

• 時間計算量: \(O(N + Q)\)
  （初期カウント \(O(N)\)、各更新は定数回比較で \(O(1)\)）
• 空間計算量: \(O(N + Q)\)
  （文字列配列と出力バッファ）

実装のポイント

• 文字列は更新しやすいように list で持つ。

• 入力の位置は1-indexなので、コード内では i = int(i_str) - 1 に変換する。

• 更新時は必ず「変更前の情報」で減算し、「変更後の情報」で加算する。

• old == c のとき差分計算をスキップすると、無駄な比較を減らせます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    S = list(input().strip())

    same = 0
    for i in range(N - 1):
        if S[i] == S[i + 1]:
            same += 1

    out = []
    for _ in range(Q):
        i_str, c = input().split()
        i = int(i_str) - 1

        old = S[i]
        if old != c:
            if i - 1 >= 0:
                if S[i - 1] == old:
                    same -= 1
                if S[i - 1] == c:
                    same += 1
            if i + 1 < N:
                if old == S[i + 1]:
                    same -= 1
                if c == S[i + 1]:
                    same += 1
            S[i] = c

        out.append(str(same))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

この解説は gpt-5.3-codex によって生成されました。