Подсчет инверсий в диапазонах

Ответ 1

Здесь используется алгоритм O ((n + m) sqrt n log n) -time. Это, вероятно, недостаточно хорошо для прохождения, но что-то кажется не совсем правильным - обычные трюки для конкурса программирования не работают. (O ((n + m) sqrt n) может быть достижимо с большей осторожностью.)

Разделите входной массив на sqrt n subarrays длины sqrt n, называемых блоками. Используя инкрементный алгоритм подсчета инверсий, для каждой пары, состоящей из блока и префикса массива, вычислите количество инверсий, в которых первый элемент поступает из первого, а второй - из последнего. (O (n sqrt n log n)) Сделайте то же самое для пар префикс-блоков.

Для каждого диапазона ввода разложите его на объединение некоторых блоков (заблокированных элементов) и меньше 2 элементов sqrt n (разблокированные элементы). Используя предварительно вычисленные результаты и исключение включения, найдите количество инверсий в диапазоне, где заблокирован хотя бы один элемент. (O (sqrt n)) Вычислите и добавьте к этой величине количество инверсий в диапазоне, включающем два разблокированных элемента. (O (sqrt n log n))

Ответ 2

O ((n + m) * sqrt (n) * log (n)) время, O (n + m) пространственный алгоритм с автономными запросами (все диапазоны запросов должны быть известны заранее):

• Разделите массив A на приблизительно равные части sqrt (n).
• Для каждой части массива выполните шаги 3... 7.
• Инициализировать 3 указателя (Pbegin, Pmid, Pend), чтобы все они указывали на конец текущей части массива (или даже лучше на право начало диапазона, принадлежащего этой части).
• Advance Pend; обновить дерево статистики по порядку, которое определяет количество инверсий между Pmid и Pend; когда Pend совпадает с концом некоторого диапазона, который начинается в текущей части массива, выполните шаги 5... 7.
• Переместите Pbegin назад, пока он не совпадает с началом диапазона, найденным на шаге 4. Накопите количество элементов в дереве статистики порядка меньше значений, обозначенных символом Pbegin (но не обновляйте дерево).
• Найдите количество инверсий между Pbegin и Pmid (используя либо сортировку слияния, либо отдельное дерево статистики по порядку).
• Добавьте вместе количество инверсий, найденное на шагах 4, 5, 6. Это число инверсий для текущего диапазона.

Дерево BIT/Fenwick можно использовать здесь как эффективную реализацию дерева статистики порядка. В этом случае необходима некоторая предварительная обработка: подставлять значения массива их индексами в отсортированную копию массива для сжатия диапазона значений.

O ((n + m) * sqrt (n)), O (n * sqrt (n)) пространственный алгоритм с онлайновыми запросами. Как намекнул Дэвид Эйзенстат.

Предварительная обработка:

• Подставлять значения массива по их индексам в отсортированную копию массива для сжатия диапазона значений.
• Разделите массив A на приблизительно равные части sqrt (n).
• Для каждой части B массива выполните шаги 4... 8.
• Zero-initialize bitet размером 'n'. Переключить биты, соответствующие значениям части "B". Для этого битового набора вычислительных массивов префиксов sum P и массива суффиксных сумм S.
• Для каждой части C предшествующей части B выполните шаг 6.
• Начиная с последнего значения v части C и возвращаясь назад, соедините все значения P[v] и напишите sqrt(n) результаты в таблицу поиска E. Сложностью этого шага является O (n * sqrt (n)).
• Для каждой части D следующая часть B выполните шаг 8.
• Начиная с первого значения v части D и переходя вперед, соедините все значения S[v] и напишите sqrt(n) результаты в таблицу поиска F. Сложностью этого шага является O (n * sqrt (n)).
• Использовать инкрементный алгоритм (дерево Фенвика) для подсчета числа инверсий во всех суффиксах блока (все подмассивы, начинающиеся с границы блока с длиной не более sqrt(n)). Запись результатов в таблицу поиска G. Сложностью этого шага является O (n * log n).
• Используйте инкрементный алгоритм для подсчета количества инверсий во всех префиксах блоков. Запись результатов в таблицу поиска H. Сложностью этого шага является O (n * log n).
• Используйте любой из E или F и любой из G или H для вычисления числа инверсий в последовательных блоках (с любой парой блоков для начальных и конечных позиций). Запись результатов в таблицу поиска R. Сложностью этого шага является O (n).

После предварительной обработки у нас есть несколько LUT, содержащих число инверсий в префиксах/суффиксах блоков (G, H, O (n)), количество инверсий между полными блоками и префиксы/суффиксы блоков (E, F, O (n * sqrt (n)) пробел) и количество инверсий в последовательных блоках (R, O (n) пробел). (Возможно, мы могли бы объединить E и F с R, что увеличивает время предварительной обработки, но позволяет O (1) время для первого шага запроса).

Query:

• Используйте R для получения числа инверсий в последовательных полных блоках, используйте E и F, чтобы добавить количество инверсий между префиксом/суффиксом и каждым из этих полных блоков, используйте G и H для добавьте количество инверсий в префикс и в суффикс.
• Чтобы получить количество инверсий между префиксами и суффиксами, выполните сортировку как с помощью сортировки radix (sqrt(n) счетчиков, 2 счетных прохода, так и 2 прохода для распределения значений) и слейте их.
• Добавьте значения из шагов 1 и 2, чтобы получить количество инверсий для диапазона запросов.

Ответ 3

Третий диапазон: индексы 0 - 3 содержат 1-й и 2-й диапазоны.

Если вы знаете, сколько инверсий содержалось в предыдущих диапазонах, вы пропускаете их. Итак, во время третьего диапазона вы можете пропустить сравнение с 1 по 2 и пропустить сравнение с 2 по 3.

Итак, во время 3-го диапазона вы сравниваете только

 0 -> 1
 0 -> 2
 0 -> 3
 1 -> 3

Что делает наилучший сценарий O (nlogn) и худший сценарий O (mnlogn).

Ответ 4

Здесь выработка предыдущего ответа, также с заполненным потенциальным зазором. Сначала вы вычисляете и сохраняете количество инверсий для всех префиксов вашего массива в O (n log n) времени, добавляя один элемент за раз справа налево и выполняя поиск двоичного поиска, чтобы найти элемент в дереве все предыдущие элементы для определения дополнительного количества добавленных инверсий, а затем вставьте элемент в двоичное дерево (и сохраните дерево как самобалансирующееся двоичное дерево поиска). Затем вы также вычисляете и сохраняете количество инверсий во всех суффиксах. Затем, если вы хотите подсчитать количество инверсий в диапазоне [L, R], вы добавляете инверсии для префикса, начиная с L, в инверсии в суффиксе, заканчивающемся на R, и вычитаете общее количество инверсий для всего массив. Это почти дает вам ответ, но не совсем, потому что он дает вам ответ за вычетом количества инверсий между диапазонами [1, L-1] и [R + 1, n]. Таким образом, вам нужно вычислить количество инверсий между произвольной строкой префикса и суффикса в вашем массиве. Для этого вы вычисляете количество инверсий между произвольными префиксами и суффиксами, начинающимися с кратного sqrt (n). Вы можете сделать это в O (n ^ (3/2) log n) времени, отсортировав каждый суффикс, а затем для каждого суффикса добавив один элемент в префикс слева направо, выполнив двоичный поиск в суффиксе, чтобы выяснить сколько добавить к числу инверсий. Точно так же вы вычисляете и сохраняете количество инверсий между каждым префиксом, заканчивающимся кратным sqrt (n), и каждый элемент справа от префикса в O (n ^ (3/2) log n).

Затем для данного диапазона вы берете префикс и суффикс и округлите суффикс до конца в ближайшем кратном sqrt (n) выше и просматриваете количество инверсий в O (1) раз. Затем вы берете оставшиеся элементы в суффиксе и просматриваете количество инверсий в префиксе, которое заканчивается ближайшим кратным sqrt (n) ниже, в O (sqrt (n)) времени. Затем вы берете остальные элементы в суффиксе и остальные элементы в префиксе (не включены в конечные точки sqrt (n)), а грубая сила вычисляет количество инверсий между ними в O (sqrt (n) log n) time, Общее время вычислений равно O (sqrt (n) log n) для диапазона, что дает общее время выполнения O ((m + n) sqrt (n) log n), которое должно удовлетворять 1-секундному временному пределу.