V-Sort

将每个位置视为顶点，每种允许的交换对应一条无向边。通过边上的交换，可以在同一连通分量内实现任意排列。因此，可行的充要条件是每个分量中当前值的多重集合与目标值的多重集合相同。位置 $A_i,B_i$ 的目标值均为 $i$。

• 子任务 1（$X=Y=0$）：只能交换 $A_i,B_i$。两者的目标值都是 $i$，所以所有位置必须原本就正确。时间复杂度为 $O(N)$。
• 子任务 2（$X=Y=1$）：两个分量分别为 $A_1,B_2,A_3,B_4,\ldots$ 与 。每个分量中 到 必须各出现一次。统计频次，时间和空间复杂度均为 。 时，它们是两个孤立顶点。
• 子任务 3（$X=0$）：$Y=0$ 时同子任务 1。$Y>0$ 时，$A_i,B_i$ 相连，且下标可相差 的倍数，所以各分量对应下标模 的余数类。检查位置 上的值 是否满足 ，并检查每个值在两个序列中总共出现两次。时间和空间复杂度均为 。
• 子任务 4（$N\leq5$）：朴素解法在 $2N$ 个位置上用 Floyd–Warshall 算法计算连通性，再将每个分量的当前值和目标值分别排序比较。时间复杂度为 $O(N^3)$，空间复杂度为 $O(N^2)$。
• 子任务 5（$N\leq3\,000$）：建立邻接矩阵，用 DFS 求连通分量，每个顶点扫描所有可能的邻点，再比较分量中的频次。时间和空间复杂度均为 $O(N^2)$。文件内 $\sum N\leq3\,000$，所以 。
• 子任务 6：每个顶点至多有两个邻点，可以由下标直接计算，无需邻接矩阵。用非递归 DFS 求分量，对当前值的频次加一，对目标值的频次减一。检查并重置本分量访问过的条目，不能每次清空整个数组。时间和空间复杂度均为 $O(N)$。

$X=N$ 或 $Y=N$ 时，相应类型的边不存在。孤立顶点也必须检查。允许重复值，因此仅比较元素和是不够的。完整解法总时间复杂度为 $O(\sum N)$。所有下标和频次的绝对值不超过 $1\,000\,000$，无需超出 64 位有符号整数范围的运算。

Solution written by GPT