Để hiểu cách giải bài này, bạn đọc cần hiểu cách giải bài String Mood khi không có phép cập nhật.

Với mỗi phép cập nhật, ta có thể làm một cách ngây thơ bằng cách cập nhật lại ma trận thứ ~i~ (đại diện cho kí tự thứ ~i~ của xâu) với độ phức tạp thời gian ~O(1)~, sau đó nhân lại các ma trận từ ~1~ đến ~n~ để tính đáp án với độ phức tạp thời gian ~O(n)~. Tuy nhiên, cách làm này không đủ nhanh.

Dễ dàng nhận thấy ta có thể tối ưu độ phức tạp thời gian của phép cập nhật điểm (point update - thay đổi ma trận thứ ~i~) và truy vấn đoạn (range query - tích các ma trận trong đoạn) thành ~O(log\:n)~ bằng Cây Phân Đoạn (Segment Tree). Bạn đọc tìm hiểu thêm về cách cài đặt Cây Phân Đoạn tại đây hoặc tại đây.

Lưu ý thứ tự phép nhân (từ trái sang phải) khi cài đặt cây phân đoạn do phép nhân ma trận không có tính chất giao hoán. Ngoài ra, do chúng ta chỉ cần truy vấn đoạn ~[1,n]~ nên chỉ cần in ra đáp án chứa trong nút lớn nhất của cây phân đoạn.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;
const int nax = 2e5 + 5;
const int mod = 1e9 + 7;
char s[nax];
#define REP(i) for(int i = 0; i < 2; ++i)

struct Matrix {
    int a[2][2] = {{0,0},{0,0}};
    Matrix operator *(const Matrix& other) const {
        Matrix product;
        REP(i) REP(j) REP(k) {
            product.a[i][k] = (product.a[i][k] + (long long) a[i][j] * other.a[j][k]) % mod;
        }
        return product;
    }
    void init(char match) {
        REP(i) REP(j) {
            a[i][j] = 0;
        }
        for(char ch = 'A'; ch <= 'Z'; ++ch) {
            if(match == '?' || ch == match) {
                if(ch == 'H') { // everthing moves to happy
                    a[0][1]++;
                    a[1][1]++;
                }
                else if(ch == 'S' || ch == 'D') {
                    a[0][0]++;
                    a[1][0]++;
                }
                else if(ch == 'A' || ch == 'E' || ch == 'I' || ch == 'U' || ch == 'O') {
                    a[0][1]++;
                    a[1][0]++;
                }
                else {
                    a[0][0]++;
                    a[1][1]++;
                }
            }
        }
    }
};

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

    int BASE = 1;
    while(BASE < n) {
        BASE *= 2;
    }
    vector<Matrix> tree(2 * BASE);
    for(int i = 0; i < n; ++i) {
        tree[BASE+i].init(s[i]);
    }
    for(int i = n; i < BASE; ++i) {
        tree[BASE+i].init('Z'); // neutral character
    }
    for(int i = BASE - 1; i >= 1; --i) {
        tree[i] = tree[2*i] * tree[2*i+1];
    }
    printf("%d\n", tree[1].a[1][1]);

    while(q--) {
        int i;
        char new_ch;
        scanf("%d %c", &i, &new_ch);
        i--;

        tree[BASE+i].init(new_ch);
        for(int x = (BASE + i) / 2; x >= 1; x /= 2) {
            tree[x] = tree[2*x] * tree[2*x+1];
        }
        printf("%d\n", tree[1].a[1][1]);
    }
}