【模板】子序列自动机

题目背景

本题中,若 $x$ 是 $y$ 的子序列,则等价于存在一个**单调递增**序列 $z$,满足 $|z| = |x|$,$z_{|x|} \leq |y|$,且 $\forall i \in [1, ~|x|],~y_{z_i} = x_i$。其中 $|x|,~|y|,~|z|$ 分别代表序列 $x,~y,~z$ 的长度,$x_i,~y_i,~z_i$ 分别代表序列 $x,~y,~z$ 的第 $i$ 项。 这是一道在 ``yLOI2020`` 备选题里被毙掉的题目。

题目描述

给定一个长度为 $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

0 5 5 5
1 3 2 2 4
3 1 5 2
2 3 2
3 1 2 3
3 1 2 4
5 1 3 2 2 4

输出样例 #1

No
Yes
No
Yes
Yes

说明

#### 样例 1 解释 - 对于第一次询问,原序列中没有 $5$,所以给定序列显然不是原序列的子序列。 - 对于第二次询问,存在两个合法的序列 $z$,分别是 $\{2,~3\}$ 和 $\{2,~4\}$。即 $a_{2} = b_{2, 1},~a_3 = b_{2, 2}$ 或 $a_2 = b_{2, 1},~a_{4} = b_{2, 2}$。这里 $b_{i, j}$ 代表序列 $b_i$ 的第 $j$ 个元素,序列 $z$ 的含义见【题目背景】,下同。 - 对于第三次询问,不存在合法的序列 $z$。 - 对于第四次询问,存在两个合法的序列 $z$,分别是 $\{1,~3,~5\}$ 和 $\{1,~4,~5\}$。 - 对于第五次询问,存在一个合法的序列 $z$,为 $\{1,~2,~3,~4,~5\}$。 #### 数据范围与约定 **本题采用多测试点捆绑测试,共有 3 个子任务**。 - Subtask 1(20 points):$type = 1$,$n, q, m \leq 100$,$\sum_{i = 1}^{q} l_i \leq 10^3$。 - Subtask 2(35 points):$type = 2$,$n,q \leq 10^5$,$m \leq 26$,$\sum_{i = 1}^{q} l_i \leq 10^6$。 - Subtask 3(45 points):$type = 3$,$n,q,m \leq 10^5$,$\sum_{i = 1}^q L_i \leq 10^6$。 对于全部的测试点,保证 $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$。 ### 提示 - 请注意常数因子对程序效率造成的影响。 - 本题输入规模较大,请注意数据读入对程序效率造成的影响。 - 请注意输入第一行的顺序为先输入询问次数 $q$,再输入序列元素最大值 $m$。