186
правок
Изменения
→Динамический convex hull trick
==Динамический convex hull trick==
Заметим, что условия на прямые, что <tex>k[i]</tex> возрастает/убывает и <tex>x[i]</tex> убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016 <ref>[1]</ref>).
Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за <tex>O(\log(n))</tex> можем найти <tex>dp[i]</tex>, но теперь вставку <tex>i</tex>-й прямой в оболочку уже нельзя выполнить описанным ранее способом за <tex>O(1)</tex> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при <tex>x \in [x1; x2]</tex>, где <tex>x1, x2 \in R</tex> - точки пересечения с некоторыми прямыми, причем <tex>x2</tex> не обязательно равно <tex>+ \infty</tex>
