数组中的大反转数
Number of big inversions in an array
我正在处理一个问题：
给定一个数组 A[1,2,...,n]，问题是计算大反转对的数量。大反转是一对索引 (i, j) 使得：2.i < j and A[i] > 2.A[j].
我们需要在 O(nlogn) 时间内解决这个问题。
我已经坚持了一段时间，并且不知道如何遵守索引 (2i < j) 约束。如果我使用合并排序之类的东西，那么，通过对两半进行排序，我将丢失关于前半部分中哪些索引满足 2i < j 的信息，并且我总是以 O(n^2) 时间结束合并步骤。
我也在考虑修改数组，比如将索引加倍，然后根据它们的索引合并两半，但也没有任何进展。
如果有人可以提供想法，我将不胜感激。谢谢！
我不确定分而治之，但我们可以从索引 n / 2 开始并向下迭代。当我们迭代时，将满足其索引大于 2*i 的元素插入到顺序统计树中。随着树的生长，每个这样的元素都会被插入一次。报告索引 i 处的每个元素树中有多少元素低于 A[i] / 2.
我正在处理一个问题：
给定一个数组 A[1,2,...,n]，问题是计算大反转对的数量。大反转是一对索引 (i, j) 使得：2.i < j and A[i] > 2.A[j].
我们需要在 O(nlogn) 时间内解决这个问题。 我已经坚持了一段时间，并且不知道如何遵守索引 (2i < j) 约束。如果我使用合并排序之类的东西，那么，通过对两半进行排序，我将丢失关于前半部分中哪些索引满足 2i < j 的信息，并且我总是以 O(n^2) 时间结束合并步骤。 我也在考虑修改数组，比如将索引加倍，然后根据它们的索引合并两半，但也没有任何进展。 如果有人可以提供想法，我将不胜感激。谢谢！
我不确定分而治之，但我们可以从索引 n / 2 开始并向下迭代。当我们迭代时，将满足其索引大于 2*i 的元素插入到顺序统计树中。随着树的生长，每个这样的元素都会被插入一次。报告索引 i 处的每个元素树中有多少元素低于 A[i] / 2.