题目链接
P5826 【模板】子序列自动机
【模板】子序列自动机
题目背景
本题中，若 \(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
样例输入 #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\)。
解题思路
序列自动机
- 时间复杂度：\(O()\)
二分
将 \(a\) 的下标用桶存下来，每次读入子序列时，都从当前值满足条件的最前面开始搜索，如果搜不到则一定不是子序列
- 时间复杂度：\(O(\sum_{i=1}^q l_i \times logn)\)
代码
- 序列自动机
- 二分
// Problem: P5826 【模板】子序列自动机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5826
// Memory Limit: 500 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
// %%%Skyqwq
#include <bits/stdc++.h>
//#define int long long
#define help {cin.tie(NULL); cout.tie(NULL);}
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int N=1e5+5;
vector<int> a[N];
int main()
{
int t,n,q,m,x,l;
scanf("%d%d%d%d",&t,&n,&q,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[x].pb(i);
}
while(q--)
{
bool res=true;
int pos=0;
for(scanf("%d",&l);l;l--)
{
scanf("%d",&x);
pos=upper_bound(a[x].begin(),a[x].end(),pos)-a[x].begin();
if(pos<a[x].size())pos=a[x][pos];
else
res=false;
}
puts(res?"Yes":"No");
}
return 0;
}