1

这就是问题所在，这里有一个解决方案。

第一部分很简单。这是我没有得到的第二部分，无论我多么努力。你基本上有两组区间，需要找到一个区间不完全在另一个区间内的所有交叉点。

我一直盯着问题设置器代码，直到我的眼睛开始流血。仍然无法理解这一点：

for(int L=n;L>=1;L--) {
   FOR(it, r[L]) add(*it, -1);
   add(L, 1);
   r[left[L]].push_back(L);
   ans += ask(right[L]-1);
}

它是如何工作的？算法是什么？

社论中指出，您可以使用区间树或“二进制索引树”来解决此问题。我或多或少地了解什么是区间树以及它如何有用。但是问题设置者显然没有使用它，并且“二进制索引树”没有出现在搜索中，而是有“二进制索引树”，它处理部分总和，我看不出它是如何相关的（它可能非常好吧，它是相关的，但我不明白如何）。

有什么帮助吗？指向我需要阅读的文学作品？

4

2 回答 2

2

HackerRank.com 网站上给出的问题之一是计算 N 个数字排列中几乎排序的区间的数量，这些数字的值范围从 1 到 N。

数组的区间被定义为任何连续的非空数字子集。例如，如果数组定义为，{ 3, 4, 1, 5, 2 }则有效区间将包括{ 5 }, { 1, 5 }, { 3, 4, 1}。

数组的几乎排序区间是如上所述的任何区间加上第一个数字小于或等于该区间中的所有其他数字并且最后一个数字大于或等于所有其他数字的要求。

使用上面的数组，几乎排序的区间集将包括{ 3, 4 }, {1, 5}, { 5 }，但不包括{ 5, 2 }。

所以整组几乎排序的区间将是-

{ { 3 }, { 3, 4 }, { 4 }, { 1 }, { 1, 5 }, { 5 }, { 2 } }

因此，几乎排序的区间数为 7。

为了迎接挑战，您的解决方案必须及时解决问题O(n * log n)。一个O(n * n)解决方案是相当微不足道的。这O(n * log n)需要更多的努力。

我发现这个问题非常困难，因为我的原件O(n * log n)非常混乱，并且觉得有更好的方法。搜索网络真的没有多大帮助，除了一些人给出了一些可怕的提示，这些提示真的没有多大帮助。当我终于偷看 HackerRank 的“编辑”部分时，一个更优雅的解决方案的描述很难阅读。经过一番努力，我终于明白了解决方案的工作原理。

定义两个数组以帮助解决在数组中查找所有几乎已排序的区间的问题：

left[i] = j其中j < i和j最接近i和a[j] > a[i]。

right[i] = j其中j > i和j最接近i和a[j] < a[i]。

这些数组有助于定义两个索引何时i构成j一个几乎排序的区间。对于某些i和，如果和j，a[i..j]是一个几乎排序的区间。j < right[i]i > left[j]

对于数组a[] = { 3, 4, 1, 5, 2 }和。请注意，我们使用左侧数组的 -1 表示左侧的越界位置，使用值 5（即 N）表示右侧的越界位置。left[] = { -1, -1, 1, -1, 3 }right[] = { 2, 2, 5, 4, 5 }

让我们考虑区间a[i..j]、 wherei=2和j=3。{1, 5}是区间。我们看到以下内容，

- j < right[i], 或3 < right[2], 或3 < 5 - i > left[j], 或2 > left[3], 或2 > -1

这意味着这个区间是一个几乎排序的区间。另一个例子是，a[2] = 1; a[1] = 4。所以，left[2] = 1。

需要注意的一件有趣的事情是，一旦我们定义left[]并right[]“编码”了数字和彼此之间的关系，我们现在可以解决仅处理数组索引而不是组成数组的数字的问题.

和数组都可以及时left[]计算。right[]O(n)

然后我们可以使用这些数组来有效地计算几乎排序的区间的总数。我们从右到左遍历索引。当我们遍历数组时，我们可以保留一个集合 B ，该集合 B 由所有可能的结束索引组成，用于从当前索引处或左侧开始的所有间隔。

这可以通过将索引值添加到 indexi处的集合并删除 index 处的索引值B（始终是 左侧的某个索引）来完成。维护设备可以及时完成。iileft[i]iBO(1)

对于每个索引，如果当前索引是开始索引，我们可以检查集合中有多少索引B是有效的结束索引。

在 index处，仅当 时i，索引j才会在集合中。如果 ，该区间是一个几乎排序的区间。我们可以计算集合中有多少个索引小于然后知道有多少几乎排序的区间索引位置对几乎排序的区间的总数有贡献（作为区间的左索引位置）。如果我们然后在所有索引中累积这些值，我们可以找到几乎排序的区间的总数。Bi > left[j]{ a[i] ... a[j] }j < right[i]Bright[i]i

这只剩下我们如何计算效率B较低的索引数量。right[i]这可以使用二进制索引树O(log n)及时完成。

因此总运行时间将be O(n * log n)。

于 2014-12-02T05:19:06.397 回答
1

好的，我知道了。这是一个二叉索引树 - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees。是的，这是相关的。

于 2014-08-12T21:46:26.113 回答