CF1783F Double Sort II

给定两个长度为 $n$ 的排列 $a$ 和 $b$。排列是一个长度为 $n$ 的数组，其中每个整数 $1$ 到 $n$ 恰好出现一次。每个排列的下标从 $1$ 到 $n$。 你可以进行如下操作任意次： - 选择一个整数 $i$，$1 \le i \le n$； - 设 $x$ 为满足 $a_x = i$ 的下标。交换 $a_i$ 和 $a_x$； - 设 $y$ 为满足 $b_y = i$ 的下标。交换 $b_i$ 和 $b_y$。 你的目标是用最少的操作次数，使得两个排列都变为升序排列（即满足 $a_1 < a_2 < \dots < a_n$ 且 $b_1 < b_2 < \dots < b_n$）。 注意，在你选择的一系列操作后，两个排列都必须是升序排列。

第一行包含一个整数 $n$（$2 \le n \le 3000$）。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$，所有 $a_i$ 互不相同）。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le n$，所有 $b_i$ 互不相同）。

首先输出一个整数 $k$（$0 \le k \le 2n$），表示将两个排列都变为升序所需的最小操作次数。可以证明，$2n$ 次操作总是足够的。 接下来输出 $k$ 个整数 $op_1, op_2, \dots, op_k$（$1 \le op_j \le n$），其中 $op_j$ 表示第 $j$ 次操作时选择的 $i$。 如果有多组答案，输出任意一组均可。

由 ChatGPT 4.1 翻译