计算两个排列中的对 (a,b) 使得 index(a) < index(b) 在两个排列中

Question

给定 (1, 2, 3,..N) 的两个排列，

Consider for n = 5

5 4 3 2 1  
3 2 4 1 5  

在两个排列中找到使 index(a)<index(b) 的对 (a,b) 的数量？
在上述情况下，答案是 4。

(4,1) index(4)<index(1) in both permutations.
(3,1) 
(2,1)
(3,2)

我们可以在 O(n ² ) 中轻松完成此操作，但我觉得我们可以在 O(nlogn) 中完成此操作。你能帮忙吗？

另一个例子...

for n = 5

3 4 1 5 2 
1 3 2 5 4

这里的答案是 5

(3,4) index(3)<index(4) in both perms.
(3,5) index(3)<index(5) in both perms.
(3,2)
(1,5)
(1,2)  

Answer 1

是的，这可以在 O( n log n ) 时间内以一种非常优雅的方式解决。由于数字本身并不重要（只是它们的索引），因此重新标记它们以便第一个排列是微不足道的；这需要 O( n ) 时间。示例中的重新标记为1 ? 3, 2 ? 5, 3 ? 1, 4 ? 2, 5 ? 4。

3 4 1 5 2 ? 1 2 3 4 5 
1 3 2 5 4 ? 3 1 5 4 2

现在 index(a) < index(b) 在第一个排列中当且仅当 a < b，所以我们只需要计算第二个排列中的对数，其中 a < b 和 index(a) < index(b) ，即按正确相对顺序排列的对的数量。这等于 ( n choose 2) 减去反转次数，可以在 O( n log n ) 时间内计算；参见例如其他 Stack Overflow Q&A。

Answer 2

这可以通过订单统计 rb tree解决。
让我们称这两个数组为a和b。（它们可以互换）
让它们的长度为n。
我们需要的逆置换p的b。（即：P [X]包含数的指标X在b）
令小号是集合与顺序统计信息。

我们将在s 中存储b已经访问过的元素的索引。 我们迭代从我= 0到n-1个（让阵列是零索引）： 数后的元素数A [1]中b是C = N-1 - P [A [1]] 。 其中，我们需要那些尚未出现在a 中的元素。这可以使用s计算。我们知道s的大小，并且在 log(n) 中我们可以计算p[a[i]]在s 中的位置。减去p[a[i]]之后的元素数


中s来自C，并将其添加到答案中。
在每次迭代结束时，我们将p[a[i]] 添加到s。

编辑：如果您使用带有 gcc 编译器的 c++，这样的集合已经实现，并用于竞争性编程。