76
правок
Изменения
м
→Обработка блока
=== Обработка блока ===
Обрабатывая блок, каждому элементу <tex>x</tex> в этом блоке взаимно однозначно сопоставим ключ <tex>y = \mathtt{key}(x);~x=\mathtt{elt}(y)</tex>. Очередь <tex>B</tex> будет работать непосредственно с ключами элементов.
Определим ключи элементов так, чтобы их значения были в промежутке <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>.
