Изменения
→Динамический convex hull trick
Заметим, что условия на прямые, что <math>k[i]</math> возрастает/убывает и <math>x[i]</math> убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).
Но рассмотрим общий случай. Наша задача поменялась следующим образом : поПо-прежнему у нас есть выпуклая оболочкапрямых, имея которую мы за <math>O(logn)</math> можем найти <math>dp[i]</math>, но теперь вставку i-й прямой в оболочку уже нельзя выполнить описанным ранее способом за <math>O(1)</math> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4: красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при <tex>x \in [x1; x2]</tex>, где <tex>x1, x2 \in \R</tex> - точки пересечения с некоторыми прямыми, причем <tex>x2</tex> не обязательно равно <tex>\infty</tex>
[[Файл:picture4convexhull.png]]
Т.е. нужно уметь быстро (за <math>O(logn)</math>?) назодитьнаходить, после какой прямой стоит пытаться вставить текущую (красную рис.4) прямую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить <math>std::set</math> (или любой аналог в других языках) пар <math><k, st></math> = <коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей.
Асимптотика решения составит <math>O(logn)</math> на каждый из n запросов «добавить прямую» + <math>O(n)</math> суммарно на удаление прямых. Итого <math>O(nlogn)</math>.
