Изменения

Заметим, что условия на прямые, что <mathtex>k[i]</mathtex> возрастает/убывает и <mathtex>x[i]</mathtex> убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).

Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за <mathtex>O(logn)</mathtex> можем найти <mathtex>dp[i]</mathtex>, но теперь вставку <tex>i</tex>-й прямой в оболочку уже нельзя выполнить описанным ранее способом за <mathtex>O(1)</mathtex> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при <tex>x \in [x1; x2]</tex>, где <tex>x1, x2 \in R</tex> - точки пересечения с некоторыми прямыми, причем <tex>x2</tex> не обязательно равно <tex>+ \infty</tex>

Т.е. нужно Чтобы уметь быстро (за <math>O(logn)</math>) находить, после какой прямой стоит пытаться вставить текущую (красную рис.4) вставлять прямую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте в множество будем хранить <math>std::set</math> (или любой аналог в других языкахпрограммирования) пар <mathtex><(k, st>)</mathtex> = <tex>(коэффицент прямой, ее номер в глобальной нумерации)</tex>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую последнюю прямую с меньшим углом наклонаугловым коэффицентом, и начиная чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает <tex>O(log(n))</tex>. Начиная с нее повторяем найденной прямой выполняем "старый " алгоритм (удаляем, пока текущая прямая бесполезнаямножества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей(удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа). Асимптотика решения составит <mathtex>O(logn)</mathtex> на каждый из <tex>n </tex> запросов «добавить прямую» + <mathtex>O(n* log(n))</mathtex> суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает <tex>O(log(n))</tex> времени. Итого <math>O(nlogn)</math>.