1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <unordered_map>

std::unordered_map<std::string, int64_t> m;
int64_t score = 0;

void collect(const char *word, std::string prefix, int64_t val, int32_t force_i) {
    if (word[0] == '\0') {
        return;
    }
    if (force_i != 0) {
        collect(word + 1, prefix, val, force_i - 1);
    }
    prefix += word[0];
    if (force_i <= 0) {
        m.try_emplace(prefix, 0);
        m[prefix] += val;
        if (m[prefix] >= 2 && m[prefix] - val < 2) {
            score += 1;
        } else if (m[prefix] < 2 && m[prefix] - val >= 2) {
            score -= 1;
        }
    }
    collect(word + 1, prefix, val, force_i - 1);
}

constexpr int64_t XD = 998'244'353; // not that it matters for the brute lol

int main() {
    int32_t n, q;
    std::cin >> n >> q;

    std::string w;
    std::cin >> w;

    collect(w.c_str(), "", 1, -1);
    std::cout << score % XD << "\n";

    for (int32_t i = 0; i < q; ++i) {
        int32_t p;
        char z;
        std::cin >> p >> z;
        p -= 1;

        if (w[p] != z) {
            collect(w.c_str(), "", -1, p);
            w[p] = z;
            collect(w.c_str(), "", 1, p);
        }
        std::cout << score % XD << "\n";
    }
}