CF2118F.Shifts and Swaps

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定长度为 $n$ 的数组 $a$ 和 $b$ ，以及一个整数 $m$ 。

数组仅包含 $1$ 到 $m$ 的整数，并且两个数组都包含了 $1$ 到 $m$ 的所有整数。

你可以对 $a$ 重复执行以下任意操作：

对数组进行一次左循环移位 $^{\ast}$ ；
如果相邻两个元素的差值至少为 $2$ ，则可以交换它们。

是否可以将第一个数组变换为第二个数组？

$^{\ast}$ 对于一个长度为 $n$ 的下标从 $0$ 开始的数组 $p$ ，其左循环移位后的数组 $q$ 满足 $q_i = p_{(i + 1) \bmod n}$ ，对于所有 $0 \le i < n$ 。

输入格式

每组测试数据包含多组测试用例。第一行包含测试用例数 $t$ （ $1 \le t \le 10^5$ ）。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $m$ （ $2 \le m \le n \le 5 \cdot 10^5$ ），表示数组的长度和 $a$ 中不同元素的个数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \le a_i \le m$ ），表示数组 $a$ 。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ （ $1 \le b_i \le m$ ），表示数组 $b$ 。

保证两个数组都包含了 $1$ 到 $m$ 的所有整数。

保证所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$ 。

输出格式

对于每组测试用例，如果可以将第一个数组变换为第二个数组，输出 "YES"；否则输出 "NO"。答案不区分大小写，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。

输入输出样例

输入#1

8
3 3
1 2 3
3 2 1
4 3
1 1 2 3
1 2 2 3
4 4
1 3 2 4
2 3 4 1
6 3
1 1 2 1 2 3
2 1 1 2 3 1
5 4
2 3 4 1 1
3 2 1 1 4
9 7
2 4 6 7 3 1 5 4 6
6 7 3 5 6 4 2 4 1
9 8
8 3 5 6 5 4 1 7 2
7 5 3 5 8 4 6 2 1
8 6
2 1 5 4 6 3 5 4
6 1 5 2 4 5 3 4

输出#1

YES
NO
YES
NO
YES
YES
NO
NO

说明/提示

在第一个测试用例中，可以通过以下步骤将数组 $a$ 变换为数组 $b$ ：

[ 1 , 2 , 3 ] — 左移一位
[ 2 , 3 , 1 ] — 交换下标 $2$ 和 $3$
[ 2 , 1 , 3 ] — 左移一位
[ 1 , 3 , 2 ] — 左移一位
[ 3 , 2 , 1 ]

在第二个测试用例中，可以证明无法通过给定的操作将数组 $a$ 变换为数组 $b$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页