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
#include <iostream>
#include <string>
#include <array>
#include <unordered_set>

namespace {
    using std::cout, std::cin, std::string;
    using std::array;
    using podslowa_t = std::unordered_set<string>;
    constexpr size_t PROG = 2;
    constexpr size_t RESZTA = 998'244'353;
    constexpr size_t ILE_LITER = 6;

    size_t ile_podslow_wielokrotnych(string const & s) {
        if (s.length() < 2)
            return 0;

        size_t ile = 0;
        podslowa_t jednokrotne(s.length()), wielokrotne(s.length());
        
        string poprz_s({s[0]});

        for (size_t i = 1; i < s.length(); ++i) {
            podslowa_t doklejane;
            for (auto x : wielokrotne) {
                x += s[i];
                doklejane.insert(std::move(x));
            }
            wielokrotne.insert(doklejane.begin(), doklejane.end());

            podslowa_t().swap(doklejane);
            for (auto x : jednokrotne) {
                x += s[i];
                doklejane.insert(std::move(x));
            }
            for (auto x : doklejane) {
                if (!jednokrotne.insert(x).second) {
                    wielokrotne.insert(x);
                }
            }
            
            auto it = jednokrotne.find({s[i]});
            if (it != jednokrotne.end()) {   
                wielokrotne.insert(*it);
                jednokrotne.erase(it);
            } else if (wielokrotne.find({s[i]}) == wielokrotne.end()) { 
                jednokrotne.insert({s[i]});
            }            
            
            it = jednokrotne.find(poprz_s);
            if (it != jednokrotne.end()) {
                wielokrotne.insert(*it);
                jednokrotne.erase(it);
            } else if (wielokrotne.find(poprz_s) == wielokrotne.end()) {
                jednokrotne.insert(poprz_s);
            }

            poprz_s += s[i];
         }

        return wielokrotne.size() % RESZTA;
    }
}

int main() {
    size_t n, q;
    string s;
    size_t pi;
    char zi;

    cin >> n >> q;
    cin >> s;
    cout << ile_podslow_wielokrotnych(s) << '\n';
    for (size_t i = 1; i <= q; ++i) {
        cin >> pi >> zi;
        s[pi - 1] = zi;
        cout << ile_podslow_wielokrotnych(s) << '\n';
    }
}