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
#include <cstdio>
#include <set>
#include <map>
#define DEBUG false
using namespace std;

struct triphash{
    long long hash_18102121071511;
    long long hash_24722820632683;
    long long hash_61246398225527;

    auto operator<=>(const triphash &other) const = default;
};

long long newhash(long long hash_mod, long long oldhash, char newletter) {
    int letter_val = newletter - 96;
    return (oldhash * 7LL + letter_val) % hash_mod;
}

triphash new_triphash(triphash old_triphash, char newletter) {
    triphash nw{};
    nw.hash_18102121071511 = newhash(18102121071511LL, old_triphash.hash_18102121071511, newletter);
    nw.hash_24722820632683 = newhash(24722820632683LL, old_triphash.hash_24722820632683, newletter);
    nw.hash_61246398225527 = newhash(61246398225527LL, old_triphash.hash_61246398225527, newletter);
    return nw;
}

char word[50001];

void rebuild_map(int n) {
    // builds map based on the `word` array;
    // outputs result

    map<triphash, long long> counts;

    triphash empty_seq{};
    counts[empty_seq] = 1;

    for (int i = 0; i < n; ++ i) {
        char next_letter = word[i];
        if constexpr(DEBUG) printf("Adding letter %c\n", next_letter);
        map<triphash, long long> oldcounts = counts;
        for (auto [x, y]: oldcounts) {
            if constexpr(DEBUG) printf("  to hash %lld (%lld) -> %lld\n", x.hash_18102121071511, y, new_triphash(x, next_letter).hash_18102121071511);
            counts[new_triphash(x, next_letter)] += y;
        }
    }

    long long twos = 0;
    for (auto [x, y]: counts) {
        if constexpr(DEBUG) printf("Hash %lld: val %lld\n", x.hash_18102121071511, y);
        if (y > 1) twos++;
    }
    printf("%lld\n", twos);
}

int main() {
    int n, q;
    scanf("%d %d\n", &n, &q);
    for (int i = 0; i < n; ++i) {
        scanf("%c", &word[i]);
    }
    rebuild_map(n);
    for (int qi = 0; qi < q; ++qi) {
        int a;
        char c;
        scanf("%d %c", &a, &c);
        word[a-1] = c;
        rebuild_map(n);
    }
    return 0;
}