需要最少的交換量，所以沒有數字的兩個鄰居都是更大的..？

Question

問題說明如下：給定一個N < 500 000個不同數字的列表，找到所需的相鄰元素的最小交換次數，以使沒有數字具有兩個較大的鄰居。一個號碼只能與鄰居交換。
提示：使用分段樹或fenwick樹。

我真的不知道我應該如何使用總和樹來解決這個問題。

實施例輸入：

Input 1: 
5 (amount of elements in the list) 
3 1 4 2 0 

output 1: 1 

input 2: 
6 
4 5 2 0 1 3 

output 2: 4 

Answer 1

我能做到在爲O（n log n）的時間和O（n）的額外的空間。但是，首先讓我們來看看在二次方程式解答我在早些時候暗示：

• 初始化結果累加器0

• 而輸入列表中有兩個以上的元素

  • 找到最低的元素在列表中
  • 將其從列表較近端添加到累加器的距離
  • 從列表中刪除元素。
• 輸出累加器。

爲什麼這樣嗎？首先，我們來看看一個需要零交換的序列是怎樣的。由於沒有重複，如果最低元素是任何地方，但是在任何一端，它都被兩個元素包圍，這兩個元素都更大，違反了要求，因此最低元素必須位於其中一個末端。遞歸到排除此元素的子序列中。爲了使序列進入這種狀態：至少需要像貪婪算法那樣涉及最低元素的交換，以將最低元素移動到一端，並且由於涉及最低元素的交換不會改變其餘的相對順序，也沒有懲罰將他們重新排列在前面。

不幸的是，只用一個列表實現這個是二次的。你如何加快速度？有一個跟蹤每個子樹的子樹權重和最小值的指樹，並在刪除個別最小值時更新這些樹：

初始化樹：首先，將列表中的每個元素都視爲一個元素子列表最小值等於它的值。然後，當你有多個子列表時，將這些子序列成對分組，建立一個子序列樹。序列的長度是兩個半部的長度的總和，其最小值等於來自兩個半部的最小值的較小值。

要從亞序列，而序列中跟蹤其索引中刪除的最小值：

• 減小子序列
• 的長度刪除從取其一半的最小的最小等於該子序列的最小
• 新的最小值是其兩半的新最小值中的較低者
• 最小值的指數等於其各自一半的指數，如果最小值在右半部分，則加上左半部分的長度。
• 從一端開始的距離等於索引或（刪除前的長度 - 索引-1），以較低者爲準。