Изменения
→Динамический 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).
[[Файл:picture4convexhull.png]]
