需要最少的交换量，所以没有数字的两个邻居都是更大的..？

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），以较低者为准。