【线段树维护DFA】cf Deltix Round autumn E

遇到一道用线段树维护有限状态自动机的题,感觉还是很巧妙的(虽然我是小蜗蜗说这套题出得不行)

看的这位大佬的讲解

原题

题目大意:每次都会修改一个abc字符串中的某个字符求每次你要修改abc中的最少个数求得不包含abc的子序列。

考虑一个串不更改怎么做，我们可以看做是一个有限状态自动机，从左往右跑转移，然后根据当前字符是多少确定转移状态。eg:当前是0状态，a字符，那么从0->0代价1，0->1代价0，2->3代价1，2->2代价0，1->3代价inf(不可能转移)。

然后我们考虑线段树合并那么设f[i][j]表示从i转移到j所需的最小代价，那么合并时类似floyd,f[i][j]=min(fl[i][k]+fr[k][j])就可以了。

#include 

using namespace std;
const int maxn = 4e5 + 5;
const int inf = 0x3f3f3f3f;
struct mtx {
    int a[4][4]; // cost from a to b
    mtx operator+(mtx bb) {
        mtx o;
        for (int i = 0; i <= 3; i++) {
            for (int j = i; j <= 3; j++)
                o.a[i][j] = inf;
        }
        for (int k = 0; k <= 3; k++) {
            for (int i = 0; i <= k; i++) {
                for (int j = k; j <= 3; j++) {
                    o.a[i][j] = min(o.a[i][j], a[i][k] + bb.a[k][j]);
                }
            }
        }
        return o;
    }
} z[maxn];

int n, q, PS[maxn];
char ss[maxn];
void init(int p, int pos) {
    switch (ss[pos]) {
    case 'a':
        z[p].a[0][0] = 1;
        z[p].a[0][1] = 0;
        z[p].a[0][2] = z[p].a[0][3] = z[p].a[1][3] = inf;
        z[p].a[1][1] = z[p].a[2][2] = z[p].a[3][3] = 0;
        z[p].a[1][2] = z[p].a[2][3] = 1;
        break;
    case 'b':
        z[p].a[1][1] = 1;
        z[p].a[1][2] = 0;
        z[p].a[0][2] = z[p].a[0][3] = z[p].a[1][3] = inf;
        z[p].a[0][0] = z[p].a[2][2] = z[p].a[3][3] = 0;
        z[p].a[0][1] = z[p].a[2][3] = 1;
        break;
    case 'c':
        z[p].a[2][2] = 1;
        z[p].a[2][3] = 0;
        z[p].a[0][2] = z[p].a[0][3] = z[p].a[1][3] = inf;
        z[p].a[0][0] = z[p].a[1][1] = z[p].a[3][3] = 0;
        z[p].a[0][1] = z[p].a[1][2] = 1;
        break;
    }
}
void maketree(int p, int l, int r) {
    if (l == r) {
        init(p, l);
        PS[l] = p;
        return;
    }
    int mid = (l + r) >> 1;
    maketree(p << 1, l, mid);
    maketree(p << 1 | 1, mid + 1, r);
    z[p] = z[p << 1] + z[p << 1 | 1];
}

int main() {
    scanf("%d%d", &n, &q);
    scanf("%s", &ss[1]);
    maketree(1, 1, n);
    int x;
    char ch;
    for (int i = 1; i <= q; i++) {
        scanf("%d %c", &x, &ch);
        ss[x] = ch;
        init(PS[x], x);
        int p = (PS[x] >> 1);
        while (p) {
            z[p] = z[p << 1] + z[p << 1 | 1];
            p >>= 1;
        }
        printf("%d\n", min(z[1].a[0][0], min(z[1].a[0][1], z[1].a[0][2])));
    }
    return 0;
}