76
правок
Изменения
→Обработка блока: Дополнил идею
=== Обработка блока ===
Определим ключи элементов так, чтобы их значения были в промежутке <tex>\{1,2,\dots,2m\}</tex>. Работая с блоком <tex>C_j</tex>, будем сливать элементы, ключи которых находятся в очереди <tex>B</tex>, с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>. Поскольку мы предположили, что <tex>m\geqslant k</tex>, то количество ключей в <tex>B</tex> не больше <tex>m</tex>, тогда длина <tex>\mathtt{merged}</tex> не больше <tex>2m</tex>, что позволяет однозначно определить ключи на множестве <tex>\{1,2,\dots,2m\}</tex>. Как было замечено ранее, элементы, чьи ключи находятся в <tex>B</tex>, располагаются в возрастающем порядке, поэтому возможно производить тривиальную операцию [[Сортировка слиянием#Принцип работы#Слияние двух массивов | слияния]] за <tex>O(m)</tex>.
В итоге, получим отсортированный список <tex>\mathtt{merged}</tex>. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливо утверждение, что <tex>(\pi_{i}<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<\mathtt{key}(\pi_{k}))</tex>, где <tex>\pi_{i},\pi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов.
Простым проходом по отсортированному блоку находим последовательность ключей соответствующую его элементам. Действуя на эту последовательность перестановкой <tex>\xi</tex>, получаем последовательность ключей в порядке исходного блока.
После того, как мы определили новые ключи для элементов, обновляем ключи в очереди <tex>B</tex>.
* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{elems}</tex>.
* Сливаем элементы в <tex>\mathtt{elems}</tex> со следующим отсортированным блоком в список <tex>\mathtt{merged}</tex>.
* Присваиваем новые ключи элементам в порядке списка <tex>\mathtt{merged}</tex> и находим ключи в порядке исходной последовательности, действуя на последовательность ключей в сортированном блоке перестановкой <tex>\xi</tex>.
* Вставляем в <tex>B</tex> новые ключи элементов списка <tex>\mathtt{elems}</tex>.
* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами <tex>\mathtt{elt}(x)</tex>.
