题目详解：F. Shifts and Swaps

---

一、问题重述

给定两个长度为 $n$ 的数组 $a$ 和 $b$，以及一个整数 $m$（$2 \le m \le n$）。数组元素取值范围为 $1$ 到 $m$，且两个数组都包含从 $1$ 到 $m$ 的所有整数（可以有重复）。

允许两种操作：

1. 循环左移：将整个数组向左循环移动一位。
2. 交换相邻元素：只有当两个相邻元素的差的绝对值 $\ge 2$ 时才能交换。

问：能否通过若干次操作将数组 $a$ 变成数组 $b$？

---

二、操作的性质分析

2.1 循环左移的性质

循环左移可以看作是在环上旋转整个数组。设数组长度为 $n$，索引从 $0$ 到 $n-1$，左移一次后，原来在位置 $i$ 的元素移动到位置 $(i-1) \bmod n$。

关键性质：

• 循环左移不改变元素之间的循环相邻关系（即环上顺序）
• 通过多次左移，我们可以将任意一个元素移动到任意位置，但会保持环上的相对顺序不变

2.2 相邻交换的性质

交换条件：$|a[i] - a[i+1]| \ge 2$

重要观察：

• 如果两个数值相差 $1$（如 $x$ 和 $x+1$），它们不能直接交换
• 如果两个数值相差 $\ge 2$，它们可以自由交换（就像冒泡排序中的相邻交换）

这意味着：

• 数值相差 $\ge 2$ 的元素之间没有顺序约束，可以任意重排
• 数值相差 $1$ 的元素之间有顺序约束，它们的相对顺序在相邻交换中保持不变

---

三、转化为图论模型

3.1 建立值之间的关系图

考虑 $m$ 个值 $1, 2, \dots, m$。对于每一对相差 $1$ 的值 $(i, i+1)$，它们在交换操作中受到限制。

定义图 $G$：

• 顶点：$1, 2, \dots, m$
• 边：对于每个 $i = 1, 2, \dots, m-1$，连接 $i$ 和 $i+1$

这实际上形成了一条链（或者说一条路径图）。

3.2 约束条件

由于相差 $1$ 的值不能直接交换，它们在数组中的相对顺序（在环上）必须保持不变。

设 $S_i$ 表示值为 $i$ 的所有元素在数组中的位置集合（模 $n$ 意义下）。那么对于每个 $i = 1, \dots, m-1$，数组 $a$ 中所有 $i$ 和 $i+1$ 的循环顺序关系必须与数组 $b$ 中的一致。

更精确地说：

• 如果我们沿着环顺时针走，遇到的 $i$ 和 $i+1$ 的顺序模式在 $a$ 和 $b$ 中必须相同
• 这意味着 $a$ 可以通过一个循环旋转变成 $b$（模掉可以自由交换的部分）

3.3 关键定理

经过分析（这是本题的核心结论）：

定理：存在一个循环旋转 $k$（$0 \le k < n$），使得对每个 $i = 1, \dots, m-1$，在数组 $a$ 经过左移 $k$ 次后，所有值为 $i$ 和 $i+1$ 的元素之间的环上邻接关系与数组 $b$ 中的一致。

换句话说，我们只需要检查是否存在一个旋转，使得对于所有 $i$，$a$ 和 $b$ 中关于 $(i, i+1)$ 的顺序约束都满足。

---

四、算法设计

4.1 基本思路

1. 将数组视为环，索引 $0$ 到 $n-1$
2. 对于每个值 $x$，记录它在 $a$ 和 $b$ 中的所有出现位置（按环上顺序）
3. 对于每个 $i = 1$ 到 $m-1$，分析 $b$ 中 $i$ 和 $i+1$ 的相邻关系模式
4. 尝试找到一个旋转 $d$，使得 $a$ 旋转 $d$ 后满足所有这些模式

4.2 具体实现步骤

步骤 1：数据预处理

vector<vector<int>> pos_a(m + 1), pos_b(m + 1);
for (int i = 0; i < n; i++) {
    pos_a[a[i]].push_back(i);
    pos_b[b[i]].push_back(i);
}

步骤 2：找出 $b$ 中所有差为 $1$ 的数对的方向

对于每个 $i$，检查 $b$ 中所有位置，看 $i$ 和 $i+1$ 是否环上相邻。如果相邻，记录方向（$i$ 在 $i+1$ 左边还是右边）。

方向定义：

• 方向 $+1$：$i$ 的位置 + 1 ≡ $i+1$ 的位置（模 $n$），即 $i$ 顺时针方向下一个是 $i+1$
• 方向 $-1$：$i+1$ 的位置 + 1 ≡ $i$ 的位置（模 $n$），即 $i+1$ 顺时针方向下一个是 $i$

步骤 3：尝试所有可能的旋转

由于 $n$ 可以达到 $5 \times 10^5$，不能暴力尝试所有旋转。我们需要更聪明的方法。

优化：

• 只需尝试那些能让第一对 $(1, 2)$ 满足条件的旋转
• 这样的旋转最多有 $|pos_a[1]|$ 个（因为旋转后，$1$ 的位置必须与 $b$ 中的某个 $1$ 的位置对应）

更精确地：

• 对于 $b$ 中每对相邻的 $(1, 2)$（环上），记录它们的位置
• 对于 $a$ 中每个 $1$ 的位置 $p$，假设旋转后 $p$ 对应 $b$ 中某个 $1$ 的位置 $q$
• 由此确定旋转量 $d = (q - p) \bmod n$
• 检查这个 $d$ 是否满足所有 $i$ 的条件

步骤 4：验证旋转

对于候选旋转 $d$，检查所有 $i = 1$ 到 $m-1$：

bool check_rotation(int d) {
    for (int i = 1; i < m; i++) {
        // 检查 a 旋转 d 后，i 和 i+1 的邻接关系是否与 b 一致
        if (!check_pair(i, i + 1, d)) {
            return false;
        }
    }
    return true;
}

其中 $check\_pair(i, j, d)$ 的实现：

bool check_pair(int x, int y, int d) {
    // 获取 b 中 x 和 y 的邻接关系模式
    vector<pair<int, int>> patterns = get_adjacency_patterns(pos_b[x], pos_b[y]);
    
    // 检查 a 旋转 d 后的邻接关系是否匹配
    for (auto [pos_x, pos_y, dir] : patterns) {
        // 在 a 旋转 d 后的位置中，检查 x 和 y 是否按 dir 方向相邻
        if (!has_adjacency(pos_a[x], pos_a[y], d, dir)) {
            return false;
        }
    }
    return true;
}

4.3 算法复杂度

• 预处理：$O(n)$
• 寻找候选旋转：$O(|pos_a[1]| \cdot m)$ 在最坏情况下可能很大
• 但实际可以通过哈希或双指针优化到 $O(n + m)$

优化后的算法：

• 使用哈希表记录 $b$ 中每个 $(i, i+1)$ 的方向模式
• 对于 $a$ 中每个可能的旋转，用哈希快速验证
• 总复杂度 $O(n + m)$

---

五、更高效的实现思路

实际上，官方解法有更简洁的判断：

1. 特殊位置法：考虑数组 $b$ 中第一个元素 $b_0$，它必须对应 $a$ 中某个值为 $b_0$ 的位置
2. 由于可以循环左移，$a$ 中值为 $b_0$ 的每个位置 $p$ 都可以作为一个候选起点
3. 对于每个候选起点，检查所有差为 $1$ 的值对是否满足顺序约束
4. 由于 $n$ 和 $m$ 很大，需要 $O(1)$ 或 $O(\log n)$ 检查每个候选

关键优化：

• 只考虑那些 $b_0$ 和 $b_1$ 在 $b$ 中相邻的情况（因为差为 $1$ 时有限制）
• 如果 $|b_0 - b_1| \ge 2$，则它们可以自由交换，限制较少
• 通过哈希记录每个值在 $a$ 中的“下一个”关系，可以快速验证

---

七、结论

本题的核心在于理解：

• 差 $\ge 2$ 的元素之间可以任意交换（无限制）
• 差 $=1$ 的元素之间不能直接交换（保持环上顺序）
• 问题转化为判断是否存在一个循环旋转，使得所有差为 $1$ 的值对在 $a$ 和 $b$ 中的顺序一致

最终算法可以在 $O(n + m)$ 时间内解决，总 $n$ 不超过 $5 \times 10^5$，完全可行。