algorithm - 如何更改合并排序以计算数组与排序数组的距离？

Question

注意:这个问题不同于反转计数问题。

数组与排序数组的距离定义为:

 dist(A)=Sumation(j-i) for any i<j that A[i]>A[j]

.简单地说，它可以在 O(n^2) 中计算。我的问题是如何更改合并排序以计算 O(n log n) 中的距离？例如:

input: 5 2 3 4 1
output: 16

我不想计算反转!此函数不同于反转。

input: 5 2 3 4 1
dist(A): 16
inversions(A): 7

Answer 1

如果你知道如何计算inversion的数量通过合并排序对数组进行排序，您将通过更改几行代码来解决此问题。

注意细节。

// struct to store the values
//
struct pa {
    int value, index;
};

// The merge step
// A is the left part, while B is the right part
// a_cnt is the number of elements in A
void merge(pa A[], pa B[], int a_cnt, int b_cnt) {
    int st = 0;
    int tmp_sum = 0;
    for (int i = 0; i < a_cnt; ++i) {
        while (st < b_cnt && B[st].value < A[i].value) {
            tmp_sum += B[st].index;
            st++;
        }
        ans += (tmp_sum - st * A[i].index)
    }

    // origional merge code here
}