题目链接：Codeforces 1150D

在中东考古研究期间，你发现了三种古代宗教的遗迹：第一宗教、第二宗教和第三宗教。你收集到了每一种宗教的演变信息，你现在想知道三种宗教是否可以和平共处。

宇宙之词是一个长度为 $n$ 的只包含小写字母的单词。在任何时候，每一种宗教都可以用一个由小写字母组成的单词来描述。

如果描述这三种宗教的单词是宇宙之词的不相交子序列，那么他们的信徒就可以和平共处。形式化地，我们能够对宇宙之词的若干位置给定一个标号 $1, 2, 3$，那么标号为 $i$ 的位置构成的单词就是第 $i$ 种宗教的描述。

然而，宗教是在不断发展的。最初，每个宗教的描述都是空的；在发展过程中，宗教进行了 $q$ 次变化。每次变化中，要么将一个字符附加到某个宗教的描述的末尾，要么从某个宗教的描述的末尾删除一个字符。每次变化后，你都需要判断宗教是否可以和平共处。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le q \le 1000$，$\lvert \text{宗教的描述} \rvert \le 250$。

Solution

我们可以很容易地想出一种单次 $O(250 ^ 3)$ 判断的方法：设 $f(i, j, k)$ 表示三种宗教描述分别匹配到第 $i, j, k$ 个位置时所需的宇宙之词的最短前缀长度。特殊地，如果无法匹配到 $i, j, k$ 则长度为 $+\infty$。

再设 $P(i, c)$ 表示第 $i$ 个位置之后（不包括第 $i$ 个位置）字符 $c$ 第一次出现的位置。特殊地，如果没有出现字符 $c$ 则位置为 $+\infty$。

那么我们可以得到转移：

$$ f(i, j, k) = \min\{P(f(i - 1, j, k), s_{1, i}), P(f(i, j - 1, k), s_{2, j}), P(f(i, j, k - 1), s_{3, k})\} $$

但是这样的复杂度是无法接受的。注意到每次只改变了 $1$ 个长度，那么我们只需要计算新增加的状态的值即可，其他状态的值是不变的。对于删除，我们只需要将非法化的状态的值全部设为 $+\infty$。

时间复杂度：$\mathcal O(250 ^ 2 \cdot q)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e5 + 5, M = 255;
const int INF = 0x7f7f7f7f;

int n, q, len[3], p[N][26], f[M][M][M];
char s[N], t[3][M];

char getc() {
    char c = getchar();
    for (; c != '+' && c != '-' && (c < 'a' || c > 'z'); c = getchar());
    return c;
}
void chkmin(int &x, int y) {
    x > y && (x = y);
}
int calc(int x, int y, int z, char c) {
    if (x < 0 || y < 0 || z < 0 || f[x][y][z] == INF) return INF;
    return p[f[x][y][z]][c - 'a'];
}
void solve(int x) {
    int l0 = (x == 0 ? len[0] : 0);
    int l1 = (x == 1 ? len[1] : 0);
    int l2 = (x == 2 ? len[2] : 0);
    for (int i = l0; i <= len[0]; i++) {
        for (int j = l1; j <= len[1]; j++) {
            for (int k = l2; k <= len[2]; k++) {
                chkmin(f[i][j][k], calc(i - 1, j, k, t[0][i]));
                chkmin(f[i][j][k], calc(i, j - 1, k, t[1][j]));
                chkmin(f[i][j][k], calc(i, j, k - 1, t[2][k]));
            }
        }
    }
}
void erase(int x) {
    int l0 = (x == 0 ? len[0] : 0);
    int l1 = (x == 1 ? len[1] : 0);
    int l2 = (x == 2 ? len[2] : 0);
    for (int i = l0; i <= len[0]; i++) {
        for (int j = l1; j <= len[1]; j++) {
            for (int k = l2; k <= len[2]; k++) {
                f[i][j][k] = INF;
            }
        }
    }
}
int main() {
    scanf("%d%d%s", &n, &q, s + 1);
    std::fill(p[n], p[n] + 26, INF);
    for (int i = n - 1; i >= 0; i--) {
        std::copy(p[i + 1], p[i + 1] + 26, p[i]);
        p[i][s[i + 1] - 'a'] = i + 1;
    }
    memset(f, 0x7f, sizeof(f));
    f[0][0][0] = 0;
    for (int i = 1; i <= q; i++) {
        char opt = getc();
        int x;
        scanf("%d", &x), x--;
        if (opt == '+') {
            len[x]++;
            t[x][len[x]] = getc();
            solve(x);
        } else {
            t[x][len[x]] = '\0';
            erase(x);
            len[x]--;
        }
        printf(f[len[0]][len[1]][len[2]] <= n ? "Yes\n" : "No\n");
    }
}