286
правок
Изменения
→List Ranking
Выкидывать по <tex>1</tex> элементу крайне неэффективно, но если выкидывать какую-то весомую часть, то нужно быстро пересчитывать веса элементов. Сделать это можно с помощью уже рассмотренного Join, однако необходимо наложить ограничение на множество удаляемых элементов: никакие два удаленных элемента не должны идти подряд в списке. В противном случае может образоваться цепочка из удаленных элементов произвольной длины. Веса всех элементов этой цепочки нужно будет прибавить к первому не удаленному элементу, что равносильно самой задаче List Ranking, которую мы и пытаемся решить.
Рассмотрим как именно изменять веса элементов. Построим и отсортируем по ключу <tex>3</tex> таблицы вида:
# Таблица <tex>Conn</tex> из пар <tex>(i, j)</tex>, где каждая пара значит что после <tex>i</tex>-ого элемента идет <tex>j</tex>-ый (может быть получена из входных данных за время линейного сканирования)
# Таблица <tex>R</tex> из пар <tex>(i, r_i)</tex>, в которой записаны ранги элементов модифицированного списка
Также пройдемся <tex>3</tex> указателями по этим таблицам. Если нам встречается триплет вида <tex>(j, i, j) \in Conn</tex>, <tex>(ij, w_iw_j) \in W</tex>, <tex>(ij, r_ir_j) \in D</tex>, то добавим пару <tex>(ji, r_i r_j + w_iw_j)</tex> в таблицу новых рангов. Однако в эту таблицу попадут все элементы, у которых следующий элемент не был удален. Поэтому далее необходимо заменить лишние записи, используя таблицу старых рангов и Join.
=== Выбор удаляемых элементов ===
