組 \((1,2),(2,3),\ldots,(N-1,N)\) のそれぞれについて、それぞれの番号のマスが一致ペアであるかが操作によってどう変わるか考えます。

\(i\) 番目のマスへ操作を行ったとき、\((i-1,i)\) と \((i,i+1)\) のペア以外の状態は変わりません。 よって、操作の前後それぞれで \((i-1,i)\) と \((i,i+1)\) の \(2\) つのペアが一致ペアかどうかを確認し、この結果によって現在の一致ペアの個数を更新することでこの問題を高速に解くことができます。

時間計算量は \(O(N+Q)\) 、空間計算量は \(O(N)\) などとなります。

実装例は以下のようになります。

#include <iostream>

int main() {
    using namespace std;
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;

    // はじめの一致ペアの個数を求める
    int ans = 0;
    for (int i = 0; i + 1 < N; ++i) {
        if (S[i] == S[i + 1]) { // 等しければ
            ++ans; // 加える
        }
    }

    for (int q = 0; q < Q; ++q) {
        int i;
        char c;
        cin >> i >> c;
        --i; // 0-indexed にしておく

        // 操作の前の一致ペアの個数を引いて
        if (i > 0 && S[i - 1] == S[i]) {
            --ans;
        }
        if (i + 1 < N && S[i] == S[i + 1]) {
            --ans;
        }

        S[i] = c; // 操作して

        // 操作の後の一致ペアの個数を足す
        if (i > 0 && S[i - 1] == S[i]) {
            ++ans;
        }
        if (i + 1 < N && S[i] == S[i + 1]) {
            ++ans;
        }

        // 現在の個数を出力
        cout << ans << endl;
    }
    return 0;
}

N, Q = map(int, input().split())
S = list(input())

# はじめの一致ペアの個数を求める
ans = sum(s == t for s, t in zip(S, S[1:]))

for q in range(Q):
    i, c = input().split()
    i = int(i) - 1 # 0-indexed にしておく

    # 操作の前の一致ペアの個数を引いて
    if i > 0 and S[i - 1] == S[i]:
        ans -= 1
    if i + 1 < N and S[i] == S[i + 1]:
        ans -= 1

    S[i] = c # 操作して

    # 操作の後の一致ペアの個数を足す
    if i > 0 and S[i - 1] == S[i]:
        ans += 1
    if i + 1 < N and S[i] == S[i + 1]:
        ans += 1

    print(ans) # 現在の個数を出力