子序列自动机

和KMP类似，不过KMP处理的是子串，这里是子序列。

---

给定一个长度为 \(n\) 的正整数序列 \(a\) ，有 \(q\) 次询问，第 \(i\) 次询问给定一个长度为 \(L_i\) 的序列 \(b_i\)，请你判断 \(b_i\) 是不是 \(a\) 的子序列。序列 \(a\) 和所有 \(b_i\) 中的元素都不大于一个给定的正整数 \(m\)。

对于全部的测试点，保证 \(1 \leq n, m, q \leq 10^5\)，\(1 \leq a_i, b_{i, j} \leq m\)，\(1 \leq l_i \leq 10^6\)，\(\sum_{i = 1}^{q} l_i \leq 10^6\)。

序列自动机

子序列自动机

\(nxt_{i,j}\) 表示 \(i\) 后面（不包括自己）第一个 \(j\) 的位置。如果没有，设成 \(n+1\)。

\(O(nm)\) 的方法如下

FOR(j,1,m) nxt[n+1][j]=n+1;
FOR(i,1,n){
    FOR(j,1,m) nxt[i][j]=nxt[i+1][j];
    if(i!=n) nxt[i][a[i+1]]=i+1;
}

用在判断子序列上的话，发现就是从 \(0\) 开始跳，每次跳到它后面第一个 \(a_i\) 的位置。看看最后是否不在 \(n+1\)。

这么贪心是因为对于所有相同的数，我们只关心能跳到的数中最前面的那个。肯定不会更劣。

但是这题中，如果开这么个两维数组，复杂度是 \(O(nm)\) 的，爆了。

标算使用的可持久化线段树，因为观察到 \(nxt_i\) 和 \(nxt_{i+1}\) 这两个数组只有一个位置不一样。时间复杂度是 \(O((n+\sum l)\log m)\)，空间复杂度是 \(O(m+n\log m)\)。

但是我们不需要真的把数组存下来。

\(i\) 后面第一个 \(j\) 的位置，只需要在所有是 \(j\) 的下标中二分就行了！

开 \(m\) 个 vector 存下这些下标，每次二分，时间复杂度是 \(O(n+(\sum l)\log m)\)，空间复杂度是 \(O(n+m)\)。

模板

#include <bits/stdc++.h>
#define rep(l, r, i) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(r, l, i) for (int i = r, END##i = l; i >= END##i; --i)
using namespace std;
#define pb push_back
// #define mpy make_pair
#define int long long
#define pii pair<int, int>
#define ps b
#define pf a

#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)

#define X(j) i[j]
#define Y(j) (dp[j] + (i[j] + L) * (i[j] + L))

#define rd read()
int read() {
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

const int N = 1e5 + 15;
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;
const int M = N * 21;

int n,m,a[N],f[N];
int s[N],q;



vector<int> v[N];
signed main(){
    rd;n=rd;q=rd;rd;
    for(int i=1;i<=n;i++) v[rd].push_back(i);
    while(q--){
        int l=rd,at=0;
        bool f=true;
        while(l--){
            int x=rd;
            if(!f) continue;
            vector<int>::iterator it=lower_bound(v[x].begin(),v[x].end(),at+1);
            if(it==v[x].end()) f=false;
            else at=*it;
        }
        puts(f?"Yes":"No");
    }
}

[FJOI2016] 所有公共子序列问题

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列 \(X=x_1x_2\ldots x_m\)，则另一序列 \(Z=z_1z_2\ldots z_k\) 是 \(X\) 的子序列是指存在一个严格递增下标序列 \(i_1,i_2, \ldots ,i_k\) 使得对于所有 \(j=1,2,…,k\) 有 \(z_j=x_{i_j}\)。

例如，序列 \(Z=\)GACT 是序列 \(X=\)GCTACT 的子序列，相应的递增下标序列为 \(1,4,5,6\)。给定两个序列 \(X\) 和 \(Y\)，当另一序列 \(Z\) 既是 \(X\) 的子序列又是 \(Y\) 的子序列时，称 \(Z\) 是序列 \(X\) 和 \(Y\) 的公共子序列。例如，若 \(X=\)GCTACT， \(Y=\)GATCCT，序列 \(T\) 是 \(X\) 和 \(Y\) 的一个公共子序列，序列 GACT 也是 \(X\) 和 \(Y\) 的一个公共子序列。注意对于任何给定的序列 \(X\) 和 \(Y\)，空序列总是它们的一个公共子序列。

所有公共子序列问题是要求对于给定的 \(2\) 个序列 \(X=x_1x_2\ldots x_m\) 和 \(Y=y_1y_2\ldots y_m\)，找出 \(X\) 和 \(Y\) 的所有不同的公共子序列。

输入格式

文件的第一行有两个正整数 \(m\) 和 \(n\)，分别表示 \(2\) 个输入序列 \(X\) 和 \(Y\) 的长度。

接下来的两行分别给出输入序列 \(X=x_1x_2\cdots x_m\) 和 \(Y=y_1y_2\cdots y_m\)，其中序列中每个元素均为二十六个英文大小写字母。

文件的最后一行给出一个非负整数 \(k\)。

\(k\) 的值为 \(1\) 时，表示计算结果要输出 \(X\) 和 \(Y\) 的所有不同的公共子序列，以及 \(X\) 和 \(Y\) 有多少个不同的公共子序列。

\(k\) 的值为 \(0\) 时，表示计算结果只要输出 \(X\) 和 \(Y\) 有多少个不同的公共子序列。

输出格式

将计算出的 \(X\) 和 \(Y\) 的所有不同的公共子序列，或 \(X\) 和 \(Y\) 有多少个不同的公共子序列输出到文件中。当 \(k=1\) 时，先输出 \(X\) 和 \(Y\) 的所有不同的公共子序列，每行输出一个公共子序列，按字典序从小到大输出。最后输出不同的公共子序列的个数。当 \(k=0\) 时，只要输出不同的公共子序列的个数。

答案....很大啦（高精度提示）