置換の部分配列が逆転した場合の置換の逆数？

Question

の数字は1からN (<=10^5)です。順列の部分配列を逆にすることができるとします。私はsummation(X*Y)を見つけなければなりません。は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 

私のアプローチは

Complexity= O(n(n+1)/2*nlogn)=O(n^3logn)はどのO(nlogn)アプローチがあり、各n*(n+1)/2サブアレーを選択し、それを逆に、それに反転を計算し、合計を行うことですか？

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 

代わり1に要素のBITエントリを設定することであり、我々は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