AtCoder ABC 372 C - Count ABC Again (3Q, 灰色, 350 点)

差分のみ更新していく系の典型問題

• 問題へのリンク

問題概要

長さ の文字列 が与えられる。次の 回のクエリに答えよ。

【クエリ】
整数 と文字 が与えられるので、 を に変更する。その後の文字列 の中に、"ABC" が何個含まれるかを答えよ。

制約

• 

考えたこと

各クエリでは 1 文字を変更するだけなので、「 全体の中で "ABC" が何個あるか」に対する影響は微々たるものなのだ。

そこで、 を更新するたびに「"ABC" の個数を改めて数える」のではなく、 を更新することで「"ABC" の個数がどのように変化するか」を求めていくことにしよう。

次の 2 ステップに分けて考えるとよい。

• "ABC" が減少する分 --- をたとえば '?' のような適当な文字に書き換えたとしたときに、"ABC" が何個減少するかを求める
• "ABC" が増加する分 --- を文字 にしたときに、"ABC" が何個増加するかを求める

これらを求めることで、"ABC" の個数の変化を求めることができる。

"ABC" が減少する分

これは次のように考えられる。

• の 文字目から 3 文字が "ABC" であるとき：1 減少する
• の 文字目から 3 文字が "ABC" であるとき：1 減少する
• の 文字目から 3 文字が "ABC" であるとき：1 減少する

"ABC" が増加する分

今度は を文字 に書き換えたあとについて、

• の 文字目から 3 文字が "ABC" であるとき：1 増加する
• の 文字目から 3 文字が "ABC" であるとき：1 増加する
• の 文字目から 3 文字が "ABC" であるとき：1 増加する

コード

以上の処理を実装すると、 の計算量となる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, Q, X;
    char C;
    string S;
    cin >> N >> Q >> S;

    int res = 0;
    for (int i = 0; i + 2 < N; i++) if (S.substr(i, 3) == "ABC") res++;
    for (int _ = 0; _ < Q; _++) {   
        cin >> X >> C, X--;

        int deg = 0, add = 0;
        if (X-2 >= 0 && S.substr(X-2, 3) == "ABC") deg++;
        if (X-1 >= 0 && S.substr(X-1, 3) == "ABC") deg++;
        if (S.substr(X, 3) == "ABC") deg++;

        S[X] = C;
        if (X-2 >= 0 && S.substr(X-2, 3) == "ABC") add++;
        if (X-1 >= 0 && S.substr(X-1, 3) == "ABC") add++;
        if (S.substr(X, 3) == "ABC") add++;

        res -= deg, res += add;
        cout << res << endl;
    }
}