Изменения
→Динамический convex hull trick
==Динамический convex hull trick==
Заметим, что условия на прямые, что k[i] возрастает/убывает и x[i] убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).
Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за <math>O(logn) </math> или быстрее можем найти dp[i], но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за <math>O(1) </math> (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине
(рис. 4).
Т.е. нужно уметь быстро (за <math>O(logn)</math>?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) примую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить std::set (или любой аналог в других языках) пар <k, st> = <коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей. Ассимптотика решения составит <math>O(logn) </math> на каждый из n запросов «добавить прямую» + O(n) суммарно на удаление прямых. Итго <math>O(nlogn)</math>.
== Альтернативный подход ==
Другой способ интерпретировать выражение <math>dp[i] = max(dp[j] + a[i] * c[j])</math> по всем их заключается в следующем: давайте перепишем выражение <math>dp[j] + a[i] * c[j] = (dp[j], c[j]) * (1, a[i])</math>, т.е. запишем ка скалярное произведение векторов <math>v[j] = (dp[j], c[j]) и u[i] = (1, a[i])</math>. Вектора <math>v[j] = (dp[j], c[j])</math> хотелось бы организовать так, чтобы за O(logn) находить максимизирующий выражение <math>v[j] * u[i]</math>. Посмотрим на рис. 5. Заметим довольно очевидный факт : красная точка(вектор) j не может давать более оптимальное значение v[j] * u[i] одновременно чем обе синие точки, т.к. v[j] * u[i] - это на самом деле проекция вектора v[j] на u[i]. По этой причине нам достаточно оставить выпуклую оболочку векторов v[j], а ответ на запрос - это поиск v[j], максимизирующего проекцию на u[i]. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из (0, 0) в (1, a[i])). Ее можно решить за O(logn) двумя бинарными или одним тернарным поиском
Ассимптотика алгоритма по-прежнему составит <math>O(n*log(n))</math>
