找到配对订单的有效方法？

Question

比方说,我有三个阵列a,b和c等长的N.每个数组的元素都来自一个完全有序的集合,但没有排序.我还有两个索引变量,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)中使用合并排序.我基本上正在寻找三个数组的推广.

为简单起见,您可以假设任何数组中没有两个元素相等(无关系).

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