algorithm - 查找配对排序的有效方法？

Question

假设我有三个数组 a , b , 和 c等长N .这些数组中的每一个的元素都来自 totally ordered set , 但未排序。我还有两个索引变量，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] in O(N log N) with a merge sort .我基本上是在寻找对三个数组的概括。

为简单起见，您可以假设任何数组中没有两个元素是相等的(没有关系)。

Answer 1

通过对数组 a 进行排序并同时重新排列数组 b 和 c，我们可以假设 a[i] < a[j] <=> i < j。所以我们需要找到对 (i,j) 的数量，使得 i < j, b[i] > b[j] 和 c[i] < c[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