前言

这是我第一次遇见如此简单易懂的"自动机"。

问题引入

给定一个长度为$n$的正整数序列$A$，有$q$次询问，每次询问给定一个长度为$l_i$序列$B_i$，问$B_i$是否为$A_i$的子序列。

$0<n,m,q\le 10^5,\sum l_i \le 10^6$

$1\le max(A_i),max(B_{ij})\le m$

做法1 - 二分查找

由于序列中的值的个数不会超过$10^5$，因此可以使用vector[i]来存放数字i（若数字的绝对值过大，离散化即可），当匹配$B_{ij}$时，通过二分查找下一个最小的$x$使得$A_x=B_{ij}$

复杂度$O(log(n)\sum l_i)$

做法2 - 可持久化线段树 (没必要)

朴素做法是使用数组$next[i][j]$表示$A_i$之后，字符$j$的位置，匹配时不断跳转即可。

直接维护该数组的复杂度为$O(\text{字符集大小}*n)$，显然不可。

观察可以发现，从$next[i]\to next[i-1]$的转移中，只有一个数据发生了变化，因而可以使用可持久化线段树维护该数组，空间复杂度$O(log_2(\text{字符集大小})*n)$，匹配的时间复杂度$O(log_2(\text{字符集大小})\sum l_i)$

Ps. 这里的字符集大小即题目中的$m$

做法3 - 思维 - 桶(离线) *

我们换个角度，让每一个$B_i$去匹配$A$：给每个串一个指针$Ptr_i$（我们令$A$的指针为$Ptr_0$，$B_i$的指针为$Ptr_i(i>0)$），一开始指针指向对应串的开头；不断向右移动指针$Ptr_0$，若$*(ptr_0)=*(ptr_i)$，则$ptr_i$右移一位。

基本思路如上，但若是每次移动$Ptr_0$都要扫一遍$Ptr_i(1\le i\le q)$，时间复杂度为$O(nq)$，显然不行。

考虑到字符集大小$m$较小，我们可以使用桶来储存对应的指针：令$Buck[x]$内装所有$*(ptr_i)=x$的指针，当$*(ptr_0)=x$，我们令桶$x$内的所有指针+1，并将指针插入到对应的新桶中，接着清空桶$x$。

---

又因为$\sum l_i$比较小，可以使用前向星来维护各个桶（见AC代码）。当然，也可以手动维护队列，稍微麻烦一点罢了。

AC代码

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
using namespace std;

const int maxn = 1e5 + 100, maxl = 1e6 + 1000;

int head[maxn], nxt[maxl], val[maxl], vcnt = 0;
int ptr[maxn], ans[maxn];
vector<int> arr[maxn];

void add(int x, int v){
    nxt[vcnt] = head[x], val[vcnt] = v;
    head[x] = vcnt++;
}

void solve(){
    int n, q, m;
    cin >> n >> n >> q >> m;

    for(int i=0; i<=m; i++) head[i] = -1;

    arr[0].resize(n);
    for(int i=0; i<n; i++) cin >> arr[0][i];
    for(int i=1, l; i<=q; i++){
        cin >> l;
        arr[i].resize(l);
        for(int j=0; j<l; j++) cin >> arr[i][j];
        add(arr[i][0], i);
    }

    for(int i=0; i<n; i++){
        int v = arr[0][i], from = head[v];
        head[v] = -1; // 清空
        for(int p=from; ~p; p=nxt[p]){
            int k = val[p];
            ptr[k]++;
            if(ptr[k] == arr[k].size()){
                ans[k] = 1;
            }else{
                // 使用前向星，无需判断arr[k][ptr[k]]==arr[k][k-1]的情况
                add(arr[k][ptr[k]], k);
            }
        }
    }

    for(int i=1; i<=q; i++){
        cout << (ans[i]?"Yes":"No") << '\n';
    }
}
  
signed main(){
    Android;
    solve();
}