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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <unordered_map>

using llu = long long int;

static const llu PRIME1 = 3074457345618258487ULL;
static const llu PRIME2 = 3074457345618258469ULL;
static const llu PRIME3 = 3074457345618258463ULL;
static const llu PRIME4 = 3074457345618258461ULL;

struct qhash {
    llu h1 = 0;
    llu h2 = 0;
    llu h3 = 0;
    llu h4 = 0;

    qhash with_appended(char c) const {
        return qhash{
            .h1 = (6 * h1 + c - '0') % PRIME1,
            .h2 = (6 * h2 + c - '0') % PRIME2,
            .h3 = (6 * h3 + c - '0') % PRIME3,
            .h4 = (6 * h4 + c - '0') % PRIME4,
        };
    }

    bool operator==(const qhash&) const = default;
};

template<>
struct std::hash<qhash> {
    size_t operator()(const qhash& q) const noexcept {
        return q.h1;
    }
};

char word[50 * 1000 + 16];

llu count_occurrences_brute(int n) {
    std::unordered_map<qhash, llu> counts, tmp;
    counts.insert({{}, 1});

    for (int i = 0; i < n; i++) {
        for (auto& [q, cnt] : counts) {
            tmp.insert({q.with_appended(word[i]), cnt});
        }
        for (const auto& [q, cnt] : tmp) {
            counts[q] += cnt;
        }
        tmp.clear();
    }

    llu ret = 0;
    for (const auto& [q, cnt] : counts) {
        if (cnt >= 2) {
            ++ret;
        }
    }

    return ret;
}

void solve_brute(int n, int q) {
    printf("%llu\n", count_occurrences_brute(n));

    for (int i = 0; i < q; i++) {
        int pos;
        char c;
        scanf("%d %c\n", &pos, &c);
        word[pos - 1] = c;

        printf("%llu\n", count_occurrences_brute(n));
    }
}

int main() {
    int n, q;
    scanf("%d %d\n", &n, &q);
    scanf("%s\n", word);

    solve_brute(n, q);

    return 0;
}