76
правок
Изменения
м
→Обработка блока
Чтобы определить ключи элементов так, чтобы их значения были в представленном промежутке, будем, работая с блоком <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>.
