我正在解决一个问题，我需要计算最长可能的交换序列的长度，以增加数组的排序值。数组的排序值定义为索引 i (1 ≤ i ≤ n) 的数量，使得 a[i] = b[i]，其中 b 是按非降序排序的数组。
我知道我需要以每次交换都会增加排序值的方式交换元素，但我正在努力想出一种有效的算法，可以在给定的约束内处理大量输入（每次测试的时间限制：2秒，每个测试的内存限制：256 MB，数组大小最大 3 * 10^5)。
到目前为止，我已经尝试了一种强力方法，执行所有可能的交换并检查排序值，但正如预期的那样，它不能很好地适应较大的数组。
有人可以建议一种更有效的方法或为我指出正确的方向吗？伪代码或高级算法真的很有帮助。
在数组中，反转是一对顺序错误的元素。例如，在 [1,2,3] 中没有反转，在 2,1,3 中有一个反转，在 3,2,1 中有 3 个。
交换次数将等于反转次数，每次交换都会撤消一次反转（按排序顺序放置一对反转对）。
您可以修改合并排序以在 O(n log n) 中计算反转，如此处所述。