给定反转的子阵列数(Number of subarrays with given inversions)

给定反转的子阵列数(Number of subarrays with given inversions)

我最近在编程比赛期间未能解决以下问题 -

给定包含n个值的数组ar[] ，您需要找到包含大于或等于k个反转的子数组的数量。

数组中的反转次数定义为索引（i，j）对的数量

1 <= i < j <= n and ar[i] > ar[j].

预计O(nlogn)最坏情况复杂性。

I recently failed to solve the following question during a programming contest -

Given an array ar[] containing n values, you need to find the number of subarrays which contains greater than or equal to k inversions.

Number of inversions in an array are defined as the number of pairs of indices (i,j) such that

1 <= i < j <= n and ar[i] > ar[j].

Worst case complexity of O(nlogn) was expected.

最满意答案

您可以在O（N log N）时间内执行此操作：

如果ar [i] ... ar [j]中存在至少K个反转，则将（i，j）定义为最小子数 ，并且在从i开始的任何较短子数组中小于K反转，即，如果移除元素是最小子阵列的末尾，那么它将具有小于K的反转。

如果（i，j）是最小子阵列，则确切地存在N + 1-j个子阵列，其至少K个倒置从位置i开始，因为向末尾添加元素从不减少反转的数量。 此外，如果有任何从i开始的> = K反转的子数组，那么从i开始只有一个最小的子数组。

所以我们要做的就是在每个位置找到最小子阵列（如果存在的话），并将相应的子阵列总数加起来，如下所示（伪代码）：

let total=0; let i,j=1,1; while(i<=N) { while (j<i || inversions in ar[i]...ar[j] < K) { ++j; if (j>N) { return total; //out of subarrays } } // (i,j) is now a minimal subarray total+=N+1-j ++i; //next start position //now, IF (i,j) has enough inversions, then it is STILL //minimal, because otherwise the previous subarray would not have //been minimal either }

为了满足我们的总复杂度目标，我们需要inversions in ar[i]...ar[j]中进行inversions in ar[i]...ar[j]以便每次迭代花费最多O（log N）。

我们可以通过将子阵列元素保持在平衡搜索树中来实现这一点，每个节点中的计数会记住该节点的子树的总大小。 当J从1增加到N时，我们将向该树添加最多N个元素，总成本为O（N log N）。 当我从1增加到N时，我们将从该树中删除最多N个元素，总成本为O（N log N）。

此外，当我们向树中添加元素时，子数组中的反转次数会增加大于我们添加的元素的数量，因为新元素位于子数组的末尾。 当我们从子阵列的开头移除一个元素时，反转的数量会减少少于我们添加的元素的数量。 这两个数字都需要O（log N）来确定，因此我们可以在O（N log N）时间内完全跟踪子阵列中的反转总量。

You can do this in O(N log N) time:

Define (i,j) as a minimal subarray if there are at least K inversions in ar[i]...ar[j], AND less than K inversions in any shorter subarray that starts at i, i.e., if you remove an element the end of a minimal subarray, then it will have less than K inversions.

If (i,j) is a minimal subarray, then there are exactly N+1-j subarrays with at least K inversions that start at position i, because adding elements to the end never decreases the number of inversions. Furthermore, if there are any subarrays with >= K inversions that start at i, then there is exactly one minimal subarray that starts at i.

So all we have to do is find the minimal subarrays at every position, if they exist, and add up the corresponding total numbers of subarrays, like this (in pseudocode):

let total=0; let i,j=1,1; while(i<=N) { while (j<i || inversions in ar[i]...ar[j] < K) { ++j; if (j>N) { return total; //out of subarrays } } // (i,j) is now a minimal subarray total+=N+1-j ++i; //next start position //now, IF (i,j) has enough inversions, then it is STILL //minimal, because otherwise the previous subarray would not have //been minimal either }

To meet our total complexity target, we need that inversions in ar[i]...ar[j] check to cost us at most O(log N) per iteration.

We can do that by keeping the subarray elements in a balanced search tree with a count in each node that remembers the total size of that node's subtree. We will add at most N elements to this tree as J increases from 1 to N, for a total cost of O(N log N). We will remove at most N elements from this tree as i increases from 1 to N, for a total cost of O(N log N).

Furthermore, when we add an element to the tree, the number of inversions in the subarray increases by the number of elements greater than the one we're adding, because the new element is at the end of the subarray. When we remove an element from the start of the subarray, the number of inversions decreases by the number of elements less than the one we add. Both of these numbers take O(log N) to determine, so we can keep track of the total amount of inversions in the subarray in O(N log N) time altogether.