高效寻找配对顺序的方法？

Question

假设我有三个长度相等的数组a、b和c。每个数组的元素来自一个全序集，但未排序。我还有两个索引变量i和j。对于所有的i != j，我想计算出满足a[i] < a[j]、b[i] > b[j]和c[i] < c[j]的索引对数量。是否有任何方法可以在小于O(N ^ 2)的时间复杂度内完成这个任务，例如通过创造性地使用排序算法？

注：这个问题的灵感是，如果你只有两个数组a和b，你可以找到索引对的数量，使得a[i] < a[j]和b[i] > b[j] 用归并排序在O(N log N)中。我基本上正在寻找三个数组的概括。

为简单起见，您可以假设任何数组的两个元素都不相等（没有平局）。

- dsimcha

---

当这个算法结束时，你希望得到一个单一的数组吗？例如，一个按排序顺序存储 a、b 和 c 中所有元素的数组？ - David Weiser

你能举个“明确定义的全序”是什么的例子吗？ - David Weiser

如果每个数组都有一个总排序，那么对于所有的 i <= j，a[i] <= a[j]，b[i] <= b[j]，c[i] <= c[j]。这是正确的吗？在这种情况下，答案不就是 |a| + |c|（因为 b[i] > b[j] 的次数为 0 吗）？ - David Weiser

@David：数组中的元素是一个完全有序集合的成员，也就是说它们可以被排序，但并没有被排序。 - Fred Foo

@David，抱歉，我应该说“对于每个数组，元素都是某些全序集合的成员”。然而，@dsimcha的措辞是更常见的表达方式。 - Fred Foo

Answer 1

通过对数组a进行排序，并同时重新排列数组b和c，我们可以假设a[i] < a[j] <=> i < j。因此我们需要找到满足i < j、b[i] > b[j] 和 c[i] < c[j]的数对(i,j)的数量。我们将(b[i], c[i])视为平面上的一个点，并逐个添加这些点。每次添加一个点(b[j], c[j])时，首先计算已添加的点(i < j)中有多少满足b[i] > b[j] 和 c[i] < c[j]的点，然后再添加点j并继续下一个点的操作。每一步得到的数字之和就是我们的结果。

现在看起来这种查询可以通过二维线段树来实现: http://en.wikipedia.org/wiki/Segment_tree 每次迭代的成本为O(log^2 n)，总复杂度为O(n log^2 n)。

（请注意，我在这里假设数组的元素是数字。这没关系，因为使用排序，我们总是可以将数组的元素替换为从1到n的数字，以保持顺序。）

编辑：实际上，一种称为Fenwick树或二进制索引树的更简单的结构就足够了。参见此链接：http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#2d

- adamax