76
правок
Изменения
→Обработка блока
Обрабатывая блоки, будем работать не со значениями элементов, а с ключами, которые определенны для каждого элемента внутри блоков. Все блоки будут обрабатываться онлайн, то есть мы не перейдём к обработке следующего блока, пока не закончим с текущим.
Каждому элементу <tex>x</tex> взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex>. Если все Все значения ключей будут находятся расположим в промежутке <tex>\{1,2,\dots,2m\}</tex>, то эффективней будет работать с ключами элементов и в очереди <tex>B</tex>будем работать со значениями ключей элементов.
Чтобы определить ключи элементам элементов так, чтобы их значения были в представленном промежутке, будем, работая с блоком <tex>C_j</tex> будем , сливать элементы, ключи которых находятся в очереди <tex>B</tex> , с <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>.Сопоставим Получим ключи, сопоставив каждому элементу в списке <tex>\mathtt{merged}</tex> его позициюв этом списке. Это и будет наш ключ. ЗаметимКак было замечено ранее, что элементы, чьи ключи находятся в <tex>B</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>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{bestelemselems}</tex>.* Сливаем элементы в <tex>\mathtt{bestelemselems}</tex> со следующим отсортированным блоком в список <tex>\mathtt{merged}</tex>.
* Присваеваем новые ключи элементам в порядке списка <tex>\mathtt{merged}</tex>.
* Вставляем в <tex>B</tex> новые ключи элементов списка <tex>\mathtt{bestelemselems}</tex>.* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответсвующими ключам элементами соответствующими ключами элементов <tex>\mathtt{elt}(x)</tex>.
Предположим, что <tex>m=5</tex>. Исходно получаем:
