CF1983D.Swap Dilemma

普及+/提高

通过率：0%

AC君温馨提醒

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

给定两个长度为 $n$ 的互不相同的正整数数组 $a$ 和 $b$ ，我们希望将这两个数组变得完全相同。当且仅当对于所有 $1 \le i \le n$ ，都有 $x_i = y_i$ 时，两个长度为 $k$ 的数组 $x$ 和 $y$ 被认为是相同的。

现在，你可以进行如下操作：选择数组 $a$ 中的某两个下标 $l$ 和 $r$ （ $l \le r$ ），交换 $a_l$ 和 $a_r$ ；然后在数组 $b$ 中选择某两个下标 $p$ 和 $q$ （ $p \le q$ ），使得 $r-l=q-p$ ，并交换 $b_p$ 和 $b_q$ 。

请判断是否有可能通过若干次操作使得两个数组完全相同。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$ （ $1 \le t \le 2 \cdot 10^4$ ），表示测试用例的组数。

每组测试用例的第一行包含一个整数 $n$ （ $1 \le n \le 10^5$ ），表示数组 $a$ 和 $b$ 的长度。

第二行包含 $n$ 个互不相同的整数 $a_1,a_2,a_3,\ldots,a_n$ （ $1 \le a_i \le 2 \cdot 10^5$ ），表示数组 $a$ 。

第三行包含 $n$ 个互不相同的整数 $b_1,b_2,b_3,\ldots,b_n$ （ $1 \le b_i \le 2 \cdot 10^5$ ），表示数组 $b$ 。

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

对于每组测试用例，如果可以通过若干次操作使得数组 $a$ 和 $b$ 完全相同，输出 "YES"；否则输出 "NO"。输出不区分大小写，例如 "yEs"、"yes"、"Yes" 和 "YES" 都被认为是肯定的回答。

输入#1

6
4
1 2 3 4
1 2 3 4
5
1 3 4 2 5
7 1 2 5 4
4
1 2 3 4
4 3 2 1
3
1 2 3
1 3 2
5
1 5 7 1000 4
4 1 7 5 1000
3
1 4 2
1 3 2

输出#1

YES
NO
YES
NO
NO
NO

在第一个测试用例中，你无需进行任何操作，因为两个数组已经相同。

在第二个测试用例中，可以证明不存在任何方法能使两个数组相同。

在第三个测试用例中，一种可行的操作方式是，首先选择 $l=1$ ， $r=3$ ， $p=1$ ， $q=3$ ，然后选择 $l=1$ ， $r=2$ ， $p=3$ ， $q=4$ 。

由 ChatGPT 4.1 翻译

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