洛谷P5826 【模板】子序列自动机题解

题意：

给定一个长度为 \(n\) 的正整数序列 \(a\) ，有 \(q\) 次询问。

第 \(i\) 次询问给定一个长度为 \(L_i\) 的序列 \(b_i\)，请你判断 \(b_i\) 是不是 \(a\) 的子序列。

序列 \(a\) 和所有 \(b_i\) 中的元素都不大于一个给定的正整数 \(m\)。

省流：给定一个主序列，每次给出一个序列，判断是否为其子序列。

输入格式：

每个测试点有且仅有一组数据。

输入的第一行是四个用空格隔开的整数，分别代表 \(type,~n,~q,~m\)。其中 \(type\) 代表测试点所在的子任务编号，其余变量的含义见题目描述。

输入的第二行是 \(n\) 个用空格隔开的整数，第 \(i\) 个数字代表序列 \(a\) 的第 \(i\) 个元素 \(a_i\)。

第 \(3\) 行至第 \((q + 2)\) 行，每行代表一次询问。第 \((i + 2)\) 行的输入格式为：

第 \((i + 2)\) 行的行首有一个整数 \(l_i\)，代表第 \(i\) 次询问的序列长度。一个空格后有 \(l_i\) 个用空格隔开的整数。该行的第 \((j + 1)\) 个整数代表序列 \(b_i\) 的第 \(j\) 个元素 \(b_{i, j}\)。

输出格式：

对于每次询问，输出一行一个字符串，若给定的序列是 \(a\) 的子序列，则输出 Yes，否则输出 No。

数据范围

保证 \(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\)。

子序列自动机（也叫序列自动机），说的特别高级，其实就是这个东西

for(int i = len - 1; ~i; i--) {
    for(int j = 0; j < 26; j++) ch[i][j] = ch[i + 1][j];
    ch[i][s[i + 1] - 'a'] = i + 1;
}

它可以维护每个位置的下一个 \(c\) 字符的位置。

但是上面的构建方式是 \(\mathcal{O}(n |\Sigma|)\) 的，只能在一些题目里使用，比如洛谷P3856 [TJOI2008] 公共子串。

注意到，在构建子序列自动机的时候，相邻两位只有一个指针不一样，其他都是一样的。

考虑对自动机进行可持久化，然后因为字符集只有 \(|\Sigma|\le 10^5\) ，我们可以构建一棵可持久化线段树

时间复杂度 \(\mathcal{O}(n \log |\Sigma|+ \sum l_i \log |\Sigma|)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int a[N], b[N];
struct Tree
{
    Tree *ls, *rs; int l, r, v;
    // build
    Tree(int _l, int _r) : l(_l), r(_r), v(-1)
    {
        if(l != r)
        {
            int mid = (l + r) >> 1;
            ls = new Tree(l, mid); rs = new Tree(mid + 1, r);
        }
    }
    // Modify
    Tree(Tree *pre, int x, int _v) : l(pre -> l), r(pre -> r), v(0)
    {
        if(l == r) v = _v;
        else
        {
            if(x <= pre -> ls -> r) { 
                rs = pre -> rs; ls = new Tree(pre -> ls, x, _v);
            }else {
                ls = pre -> ls; rs = new Tree(pre -> rs, x, _v);
            }
        }
    }
    int query(int x)
    {
        if(l == r) return v;
        if(x <= ls -> r) return ls -> query(x);
        else return rs -> query(x);
    }
} *rt[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _, n, q, m; cin >> _ >> n >> q >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    rt[n] = new Tree(1, m);
    for(int i = n; i; i--) rt[i - 1] = new Tree(rt[i], a[i], i);
    for(int len, pos; q--; )
    {
        pos = 0; cin >> len;
        for(int i = 1; i <= len; i++) cin >> b[i];
        for(int i = 1; i <= len; i++)
        {
            pos = rt[pos] -> query(b[i]);
            if(pos == -1) break;
        }
        cout << ((~pos) ? "Yes" : "No") << '\n';
    }
    return 0;
}

然后实际上这道题根本用不着这么复杂，因为字符集只有 \(10^5\) 。

我们可以把每个字符的出现位置用 vector 维护

然后对于每个询问，直接二分离当前位置最近的那个位置，使其变为当前位置

为什么选择最近的位置呢？因为选择尽可能近的位置可以产生更多的子序列

时间复杂度 \(\mathcal{O}(n+ \sum l_i \log |\Sigma|)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define upper(a, b) upper_bound(a.begin(), a.end(), b)
#define N ((int)(1e5 + 15))

int a[N], b[N];
vector<int> pos[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int _, n, q; cin >> _ >> n >> q >> _;
    for(int i = 1; i <= n; i++) { cin >> a[i], pos[a[i]].push_back(i); }
    for(int p = 0, len; q--; )
    {
        cin >> len; p = 0; bool ok = true;
        for(int i = 1; i <= len; i++) cin >> b[i];
        for(int i = 1; i <= len; i++)
        {
            auto nxt = upper_bound(pos[b[i]].begin(), pos[b[i]].end(), p);
            if(nxt == pos[b[i]].end()) { ok = false; break; } else p = *nxt;
        }
        cout << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}