algorithm - 有人可以向我解释“几乎排序的间隔”的解决方案吗？

Question

Here是个问题，here是个解决方案。
第一部分很简单。不管我怎么努力，这是我不明白的第二部分。你基本上有两组区间，需要找到所有的交叉点，其中一个区间不完全在另一个区间内。
我一直盯着问题设置代码，直到眼睛开始流血仍然不能理解这一点：

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);
}

它是如何工作的？算法是什么？
社论中提到，可以使用间隔树或“二叉索引树”来解决这个问题。我或多或少了解间隔树是什么，以及它是如何有用的但是问题设置者显然没有使用这个方法，“二叉索引树”也没有出现在搜索中，而是有一个“二叉索引树”，它处理部分和，我看不出它是如何相关的（很可能是相关的，但我不明白如何相关）。
有什么帮助吗指向我需要阅读的文学作品的指针？

Answer 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，如果a[i..j]和j < right[i]，则i > left[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处将索引值B添加到集合i中并在索引i处移除索引值left[i]来完成（索引值始终是i左侧的某个索引）。可以在B时间内维护集合O(1)。
对于每个索引，我们可以检查如果当前索引是起始索引，B集中有多少索引是有效的结束索引。
在indexi时，只有当j时，indexB才会在集合i > left[j]中。如果{ a[i] ... a[j] }，则间隔j < right[i]是一个几乎排序的间隔。我们可以计算集合B中有多少个索引小于right[i]来知道有多少几乎排序的间隔index positioni占几乎排序的间隔总数（作为间隔的左索引位置）。如果我们在所有索引中累积这些值，我们可以找到几乎排序的间隔的总数。
这只剩下如何计算B中的指数，这些指数比right[i]中的指数少这可以在O(log n)时间内使用二叉索引树来完成。
因此，总运行时间将be O(n * log n)。