algorithm - 如果排列的子数组被反转，排列中的反转次数？

Question

我有 permutation(P)数字 1至 N (<=10^5) .假设我可以反转 permutation 的子数组。我必须找到 summation(X*Y)其中 x是 P 的形式数可以通过反转 P 的任何子数组来获取和 y是这些形式的完全反转。

例如

if N =2 ; and given permutation = 2 1

Then summation(X*Y) = 

if i reverse subarray(1,1) = permutation = 2 1 inversion =1

if i reverse subarray(2,2) = permutation = 2 1 inversions =1 


if i reverse subarray(1,2) = permutation = 1 2 inversion =0 

summation (x*y) = 2*1 + 1*0 = 2 

我的方法是选择每个 n*(n+1)/2子数组并将其反转，计算其中的反转并求和，Complexity= O(n(n+1)/2*nlogn)=O(n^3logn)

有没有O(nlogn)方法？

https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)

Answer 1

tl;dr:修改用于计算反转的标准二进制索引树算法。

在伪代码中，标准算法是

# permutation is p[1..n]
inversions <- 0
let a[1..n] be a zeroed BIT
for i from 1 to n
    inversions <- inversions + sum(a[p[i]+1..n])  # sum is O(log n)-time via BIT
    a[p[i]] <- 1
end for

我们没有将元素的 BIT 条目设置为 1，而是将其设置为 i，即可以包含该元素的区间的左端点数。然后，我们将总和乘以可能包含当前元素的区间的右端点数——这是反转该对的区间数。

# permutation is p[1..n]
inversions <- 0
let a[1..n] be a zeroed BIT
let b[1..n] be a zeroed BIT
for i from 1 to n
    inversions <- (inversions
        +                               sum(b[1..p[i]-1])*(n+1-i)   # inversions created by reversal
        + sum(a[p[i]+1..n])*(n+1)*n/2 - sum(b[p[i]+1..n])*(n+1-i))  # inversions not destroyed by reversal
    a[p[i]] <- 1
    b[p[i]] <- i
end for