概要

1 回の更新で変化する可能性がある一致ペアは、更新したマスの左右にある高々 2 組だけです。
この性質を使って、一致ペアの総数を毎回 \(O(1)\) で更新していけば、全体を高速に処理できます。

考察

一致ペアとは、隣り合う 2 マスの文字が同じである組のことです。
つまり、\(1 \le i < N\) に対して \(S_i = S_{i+1}\) なら、その \(i\) が 1 つの一致ペアです。

重要な気づき

ある 1 マスだけ文字を書き換えたとき、影響を受けるのはそのマスを含む隣接ペアだけです。

位置 \(pos\) の文字を変更すると、変化する可能性があるのは次の 2 組だけです。

• \((pos-1, pos)\)
• \((pos, pos+1)\)

それ以外のペアは、その 2 文字がまったく変わらないので、一致・不一致も変わりません。

素朴な方法が遅い理由

各更新のたびに文字列全体を見て、一致ペアの数を数え直すと \(O(N)\) かかります。
これを \(Q\) 回行うと、全体で \(O(NQ)\) です。

制約は

• \(N \le 10^6\)
• \(Q \le 10^5\)

なので、最悪では \(10^{11}\) 回程度の操作になり、間に合いません。

どう解決するか

最初に文字列全体の一致ペア数を 1 回だけ数えておきます。
その後の各更新では、変更前後で影響する 2 組だけを見て個数を調整します。

具体的には、位置 \(pos\) を更新するとき：

1. 変更前に
   
   • \((pos-1, pos)\) が一致していたらカウントを 1 減らす
   • \((pos, pos+1)\) が一致していたらカウントを 1 減らす
2. 実際に文字を書き換える
3. 変更後に
   
   • \((pos-1, pos)\) が一致していたらカウントを 1 増やす
   • \((pos, pos+1)\) が一致していたらカウントを 1 増やす

こうすれば、毎回全体を見直す必要がありません。

具体例

たとえば \(S=\texttt{AABBA}\) のとき、一致ペアは

• \((1,2)\) : A と A で一致
• \((2,3)\) : A と B で不一致
• \((3,4)\) : B と B で一致
• \((4,5)\) : B と A で不一致

なので個数は 2 です。

ここで 3 文字目を A に変えると、影響するのは

• \((2,3)\)
• \((3,4)\)

だけです。

変更前： - \((2,3)\) は不一致 - \((3,4)\) は一致 → 1 減らす

変更後の文字列は AAABA なので、 - \((2,3)\) は一致 → 1 増やす - \((3,4)\) は不一致

結果として個数は変わらず 2 のままです。

アルゴリズム

1. 文字列 \(S\) の全ての隣接ペアを見て、初期状態の一致ペア数 cnt を求める。
2. 各更新について、更新位置を \(pos\) とする（実装では 0-index に直す）。
3. 更新前に、存在するなら次を確認して cnt から引く。
   • \(S_{pos-1} = S_{pos}\)
   • \(S_{pos} = S_{pos+1}\)
4. \(S_{pos}\) を新しい文字に変更する。
5. 更新後に、存在するなら次を確認して cnt に足す。
   • \(S_{pos-1} = S_{pos}\)
   • \(S_{pos} = S_{pos+1}\)
6. その時点の cnt を出力する。

この方法なら、各更新で見る場所は高々 2 組だけなので高速です。

計算量

• 時間計算量: \(O(N + Q)\)
• 空間計算量: \(O(N + Q)\)

実装のポイント

• 入力の位置 \(i_k\) は 1-indexed なので、実装では pos = i_k - 1 として 0-indexed に直しています。

• 端のマスでは存在しない隣接ペアがあるので、
  

  • 左側は pos > 0
  • 右側は pos < n - 1
    を確認してから比較します。

• Python の文字列は変更できないため、コードでは bytearray を使って 1 文字更新を高速に行っています。

• 更新後の答えをその都度 print してもよいですが、このコードでは ans にためて最後にまとめて出力しています。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    q = int(data[1])
    s = bytearray(data[2])

    cnt = 0
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            cnt += 1

    ans = []
    idx = 3
    for _ in range(q):
        pos = int(data[idx]) - 1
        c = data[idx + 1][0]
        idx += 2

        if pos > 0 and s[pos - 1] == s[pos]:
            cnt -= 1
        if pos < n - 1 and s[pos] == s[pos + 1]:
            cnt -= 1

        s[pos] = c

        if pos > 0 and s[pos - 1] == s[pos]:
            cnt += 1
        if pos < n - 1 and s[pos] == s[pos + 1]:
            cnt += 1

        ans.append(str(cnt))

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

if __name__ == "__main__":
    main()

---

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