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

Question

问题陈述如下:给定一个包含 N < 500 000 个不同数字的列表，找到所需相邻元素的最小交换次数，使得没有数字的两个邻居都更大。一个号码只能和一个邻居交换。
给出的提示:使用线段树或分域树。

我真的不知道应该如何使用求和树来解决这个问题。

示例输入:

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)，以较小者为准。