A16705. Array and Permutation
编程题
普及/提高-
知识点
题目描述
给定一个长度为 $n$ 的排列 $p$ 和一个长度为 $n$ 的数组 $a$。
“排列 $p$ 是数组 $a$ 的生成排列”是指：经过若干次（也可以为零次）以下操作之后，可以将排列 $p$ 变为数组 $a$：
每次操作可以任选一个下标 $i$（$1 \le i < n$），并执行以下两种操作之一：
- $p_i := p_{i+1}$；
- $p_{i+1} := p_i$。
换句话说，你可以选择相邻的两个元素，并将其中一个位置的值复制到另一个位置。
请你判断排列 $p$ 是否为数组 $a$ 的生成排列。
$^{\ast}$长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个不同整数以任意顺序排列的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（当 $n=3$ 时出现了 $4$）。
“排列 $p$ 是数组 $a$ 的生成排列”是指：经过若干次（也可以为零次）以下操作之后，可以将排列 $p$ 变为数组 $a$：
每次操作可以任选一个下标 $i$（$1 \le i < n$），并执行以下两种操作之一：
- $p_i := p_{i+1}$；
- $p_{i+1} := p_i$。
换句话说，你可以选择相邻的两个元素，并将其中一个位置的值复制到另一个位置。
请你判断排列 $p$ 是否为数组 $a$ 的生成排列。
$^{\ast}$长度为 $n$ 的排列是指由 $1$ 到 $n$ 这 $n$ 个不同整数以任意顺序排列的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（当 $n=3$ 时出现了 $4$）。
输入格式
每组测试数据包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。后面依次描述每组测试用例。
每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组和排列的长度。
第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），表示排列 $p$。
第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示数组 $a$。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组和排列的长度。
第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$），表示排列 $p$。
第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示数组 $a$。
保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。
输出格式
对于每组测试用例，如果排列 $p$ 是数组 $a$ 的生成排列，输出 “YES”；否则输出 “NO”。
你可以用任意大小写形式输出答案（如 "yEs", "yes", "Yes", "YES" 均可被判定为正确答案）。
你可以用任意大小写形式输出答案（如 "yEs", "yes", "Yes", "YES" 均可被判定为正确答案）。
输入输出样例
输入 #1
6 3 1 2 3 1 2 2 4 3 1 2 4 3 4 2 2 5 1 3 2 5 4 3 3 3 5 4 7 3 7 4 2 1 6 5 3 3 4 4 5 6 5 7 1 2 3 4 5 6 7 7 7 7 7 7 7 7 7 1 3 2 7 5 4 6 2 2 7 7 7 5 6
输出 #1
YES NO YES NO YES YES
说明/提示
在第一个测试用例中，数组可以通过一次操作从排列生成：
- $i=2$，执行 $p_{i+1} := p_i$。
在第二个测试用例中，不可能通过操作将 $p$ 变为 $a$。
在第三个测试用例中，需要进行两次操作：
- $i=1$，执行 $p_i := p_{i+1}$；
- $i=2$，执行 $p_{i+1} := p_i$。
- $i=2$，执行 $p_{i+1} := p_i$。
在第二个测试用例中，不可能通过操作将 $p$ 变为 $a$。
在第三个测试用例中，需要进行两次操作：
- $i=1$，执行 $p_i := p_{i+1}$；
- $i=2$，执行 $p_{i+1} := p_i$。