Может кто-нибудь объяснить мне решение "Почти отсортированные интервалы"?

Question

Здесь проблема, и здесь есть решение.

Первая часть достаточно проста. Это вторая часть, которую я не понимаю, как бы я ни старался. В основном у вас есть два набора интервалов, и вам нужно найти все пересечения, где один интервал не полностью внутри другого.

Я смотрел на кодировщик проблем, пока мои глаза не начали кровоточить. Все еще не могу понять это немного:

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

Хорошо понял. Это двоичное индексируемое дерево - http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees. И да, это актуально.

Answer 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 }, 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 set будет допустимым конечным индексом, если текущий индекс является начальным индексом.

По индексу iиндекс j будет в наборе B только если i > left[j], Интервал { a[i] ... a[j] } почти отсортированный интервал, если j < right[i], Мы можем посчитать, сколько индексов в наборе B меньше чем right[i] узнать сколько почти отсортированных интервалов индекса позиции i вносит вклад в общее количество почти отсортированных интервалов (в качестве позиции левого индекса интервала). Если затем мы накапливаем эти значения по всем индексам, мы можем найти общее количество почти отсортированных интервалов.

Это оставляет только то, как мы можем посчитать количество индексов в B которые меньше чем right[i] эффективно. Это можно сделать с помощью дерева двоичного индекса в O(log n) время.

Таким образом, общее время выполнения будет be O(n * log n),