Мне нужен алгоритм с некоторой структурой данных в Python, который на каждом шагу, когда даются два новых элемента e1, e2:
- находит позиции вставки (с сохранением порядка) первого и второго заданных элементов.
- находит максимальное значение элементов в интервале между двумя позициями вставки.
- вставляет в ранее найденную позицию вставки второго данного элемента, второй заданный элемент в паре с максимальным значением, найденным в интервале, плюс константа. Если второй данный элемент уже не был там, и в этом случае нам нужно обновить его значение только в том случае, если новое значение больше.
И этот шаг должен быть выполнен за не более чем логарифмическое время, потому что, когда этот шаг повторяется N раз, общая временная сложность в наихудшем случае не может быть далека от O(NlogN).
-- Например: my_list = [(2,1), (4,3), (5,7), (9,1)]
Как мы видим, элемент 2 соединяется с присвоенным ему значением 1, элемент 4 соединяется со значением 3, 5 соединяется со значением 7 и 9 со значением 1. И my_list упорядочен по первым элементам пар.
Теперь даны два элемента, e1 = 3, e2 = 6.
Позиция вставки в my_list (e1, ) == (3, ) — это индекс 1, а позиция вставки (6, ) — это индекс 3.
Максимальное значение, найденное в элементах my_list между индексами 1 и 3, равно 7, поскольку максимальное значение (4,3), (5,7) равно 7.
Представим, что константа, которую нужно добавить, равна 1, у нас есть: максимальное найденное значение + константа == 7 + 1 == 8. И у нас было e2 == 6, поэтому вставляемая пара — это (6, 8) с индексом 3.
И в конце этого шага my_list должен быть: [(2,1), (4,3), (5,7), (6,8), (9,1)]
-- Этот вопрос, связанный здесь, очень похож, но отличается от моего вопроса по индексу, в который вставлен элемент. В этом вопросе элемент добавляется в конец (добавляется), в моем случае вставка должна быть выполнена таким образом, чтобы сохранить порядок элементов, чтобы начало и конец следующего произвольного интервала можно было найти в логарифмическом времени . Вот почему я думаю, что, помимо использования запроса минимального диапазона, мне также нужно будет использовать некоторую расширенную структуру данных, такую как дерево интервалов или treap.
