给定逆序对数量的子数组个数

Question

我最近在编程竞赛中没能成功解决以下问题 -

给定一个包含 n 个值的数组 ar[]，你需要找到包含大于或等于 k 个逆序对的子数组数量。

数组中逆序对的数量被定义为索引对 (i,j) 的数量，满足

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

预计最坏情况下的时间复杂度为 O(nlogn)。

- LTim

---

你能添加原问题的链接吗？ - Pham Trung

当然。链接 - LTim

我认为那里给出的编辑意见是不正确的。 - LTim

似乎不太可能，一般来说。 - Untitled123

我认为那里给出的伪代码不正确，逻辑是基于伪代码的。他们使用了一棵树状数组，它只能给出小于给定数字的数量。 - LTim

Answer 1

您可以用O（N log N）的时间完成此操作：

如果ar [i] ... ar [j]中至少有K个逆序对，并且在任何以i开头的更短子数组中逆序对小于K，则将（i，j）定义为最小子数组，即如果删除最小子数组的末尾元素，则它将具有少于K个逆序对。

如果（i，j）是最小子数组，则从位置i开始至少具有K个逆序对的子数组恰好有N + 1-j个，因为向末尾添加元素永远不会减少逆序对数。此外，如果存在任何以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
}

为了实现我们的整体复杂度目标，我们需要对 ar[i]...ar[j] 中的反转进行检查，每次迭代的成本最多为 O(log N)。

我们可以通过将子数组元素保存在平衡搜索树中，并在每个节点上保留该节点子树的总大小的计数来做到这一点。当 J 从1增加到N时，我们最多将N个元素添加到此树中，总成本为O(N log N)。当i从1增加到N时，我们最多从此树中删除N个元素，总成本为O(N log N)。

此外，当我们向树中添加元素时，子数组中反转的数量会增加，因为新元素位于子数组末尾并且大于其它元素的个数；当我们从子数组开头删除一个元素时，反转的数量会减少，因为小于新添加元素的元素数量会减少。这些数字均需要O(log N)时间来确定，因此我们可以总共在O(N log N)时间内跟踪子数组中所有反转的总数量。

- Matt Timmermans