问题在这里，解决办法在这里
第一部分很简单。这是我无法理解的第二部分，无论我多么努力。你基本上有两组区间，需要找到所有交集，其中一个区间不完全在另一个区间内。
我一直盯着问题设置程序的代码，直到我的眼睛开始流血。还是看不懂这一点:
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);
}
它是如何工作的?算法是什么?
在社论中指出，您可以使用区间树或"二叉索引树"来解决这个问题。我或多或少了解间隔树是什么以及它的用处。但问题设置者显然不使用，"二叉索引树"没有出现在搜索中，而是有"二叉索引树"，它处理部分和，我没能看到它是如何相关的(很可能是相关的，但我不明白如何)。
帮忙吗?我需要阅读的文献指南?
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，如果j < right[i]和i > left[j], a[i..j]是一个几乎排序的区间。
对于数组a[] = { 3, 4, 1, 5, 2 }, left[] = { -1, -1, 1, -1, 3 }和right[] = { 2, 2, 5, 4, 5 }。注意，我们用-1表示左边数组的越界位置，用5(即N)表示右边数组的越界位置。
让我们考虑区间a[i..j]，其中i=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，该集合由从当前索引左侧或左侧开始的所有间隔的所有可能的结束索引组成。
这可以通过将索引值i添加到索引i处的B集合中，并在索引left[i]处删除索引值i(该索引始终是i左侧的某个索引)来实现。保持设置的B可以在O(1)时间内完成。
对于每个索引，如果当前索引是开始索引，我们可以检查B集合中有多少索引是有效的结束索引。
在索引i上，索引j只有在索引i > left[j]下才会出现在B集合中。区间{ a[i] ... a[j] }是一个几乎排序的区间，如果j < right[i]。我们可以计算集合B中有多少个索引小于right[i]，以了解i索引位置对几乎排序的区间总数的贡献(作为区间的左索引位置)。如果我们将这些值累加到所有的索引中，我们就可以找到几乎排序的区间的总数。
这只剩下我们如何有效地计算B中小于right[i]的索引数。这可以在O(log n)时间使用二进制索引树来完成。
因此总运行时间将是be O(n * log n) .
好的，明白了。它是一个二叉索引树- http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees。是的，它是相关的。