题解

题意简述

给定两个排列 $a$ 和 $b$（长度 $n$），允许操作：选择 $i \neq j$，同时交换 $a_i$ 与 $a_j$、$b_i$ 与 $b_j$。问能否在最多 $n$ 次操作内使得 $a$ 与 $b$ 互为逆序，即：

$$a_i = b_{n+1-i} \quad (\forall i)$$

若能，输出任意操作序列；若不能，输出 $-1$。

---

思路分析

1. 关键观察

每次操作交换位置 $i$ 和 $j$，并同时交换 $(a_i,b_i)$ 与 $(a_j,b_j)$。换句话说，每一对数 $(a_i,b_i)$ 是绑定在一起移动的，不会拆散。

最终状态要求 $a_i = b_{n+1-i}$ 对所有 $i$ 成立。因此对于位置 $i$ 和 $n+1-i$，最终状态满足：

$$(a_i,b_i) = (b_{n+1-i}, a_{n+1-i})$$

也就是说，最终排列中，$(a_i,b_i)$ 与 $(a_{n+1-i}, b_{n+1-i})$ 必须互为对方交换 $a,b$ 的值。

---

2. 必要条件的推导

在初始排列中，如果存在某对数 $(a_i,b_i)$，则最终它必须与它的“互换对” $(b_i,a_i)$ 配对（占据对称的两个位置）。这意味着：

• 对于每个 $x$，若 $(x,y)$ 存在，则 $(y,x)$ 也必须存在（且数量对称）。
• 特别地，若 $x = y$，则数对 $(x,x)$ 必须占据中心位置（当 $n$ 为奇数时）。

因此，可行性检查：

• 偶数 $n$：不能有 $(x,x)$ 这样的自配对。
• 奇数 $n$：必须有恰好一个 $(x,x)$ 自配对，其它 $2 \times \frac{n-1}{2}$ 个数对互成对称对。

若违反此条件，直接输出 $-1$。

---

3. 构造方法

我们用一个数组 $p$ 表示当前 $a$ 中每个值的下标，即 $p[a[i]] = i$。初始根据输入的 $a$ 建立 $p$。

步骤 1：处理中心（仅当 $n$ 为奇数）

令 $x$ 为那个自配对 $(x,x)$ 当前所在位置。我们需要把它移到中心位置 $\frac{n+1}{2}$。

调用 work(x, (n+1)/2)，交换位置 $x$ 和中心，同时交换对应的 $(a,b)$ 对。

---

步骤 2：处理对称配对

现在对 $i = 1 \dots \lfloor n/2 \rfloor$：

我们希望最终 $a_i = b_{n+1-i}$。当前 $a_i = i$ 吗？不一定，$i$ 只是数值，不一定在位置 $i$。但我们可以利用 $b_i$ 来定位：
我们要把 $(b_i, a_i)$ 这个对子放到对称位置。

具体操作：

• 因为 $b_i$ 在最终 $a_{n+1-i}$ 上应该等于 $b_i$ 的对称位置的值，所以现在 $b_i$ 在 $a$ 数组中的当前位置是 $p[b_i]$。
• 我们想把位置 $p[b_i]$ 上的数对与 $n+1-i$ 位置上的数对交换。

调用 work(p[b_i], n+1-i)。

这样处理后，就能保证对所有已处理过的 $j \le i$，有 $a_j = b_{n+1-j}$ 且 $a_{n+1-j} = b_j$。

---

步骤 3：操作计数

每次 work 操作只在两个不同下标执行，且每次操作计数一次。总共最多 $\lceil n/2 \rceil$ 次操作（奇数时多一次处理中心），满足题目要求 $m \le n$。

---

4. 正确性验证

通过这种贪心构造，我们逐步将每一对对称位置匹配正确，且不会破坏已经匹配好的更小的 $i$，因为每次只交换两个位置，而 $i$ 从小到大，已匹配位置是外侧，交换的内侧不会影响它们。

---

复杂度

每个测试用例 $O(n)$，所有用例总和 $n$ 不超过 $2\times 10^5$，可接受。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

const int maxn = 200100;

int n, a[maxn], b[maxn], m, p[maxn], ans[maxn][2];

inline void work(int x, int y) {
    if (x == y) return;
    ans[++m][0] = x;
    ans[m][1] = y;
    swap(a[x], a[y]);
    swap(p[a[x]], p[a[y]]);
    swap(b[x], b[y]);
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        p[a[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> b[i];
    }
    m = 0;
    int x = 0;
    // 可行性检查
    for (int i = 1; i <= n; ++i) {
        if (a[i] == b[i]) {
            if (n % 2 == 0 || x) {
                cout << "-1\n";
                return;
            }
            x = i;
        } else if (b[p[b[i]]] != a[i]) {
            cout << "-1\n";
            return;
        }
    }
    // 奇数时，将自配对移到中心
    if (n & 1) {
        work(x, (n + 1) / 2);
    }
    // 处理对称对
    for (int i = 1; i <= n / 2; ++i) {
        work(p[b[i]], n - i + 1);
    }
    // 输出
    cout << m << '\n';
    for (int i = 1; i <= m; ++i) {
        cout << ans[i][0] << ' ' << ans[i][1] << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}