Изменения

==Постановка примера задачи:== Есть n деревьев с высотами a1, a2, … an. Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так, что после уменьшения высоты спиливаемого дерева на 1 ее надо заправить. Причем стоимость заправки зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки равна ci. Изначально пила заправлена.И известны следующие ограничения : cConvex hull trick {{---}} один из методов оптимизации [n] = 0, a[1Динамическое_программирование | динамического программирования] = 1, a[i] возрастают, cиспользующий идею [i] убывают.(Задача с [codeforces.com])==Наивное решение Статические_выпуклые_оболочки:==<math>Введите сюда формулу</math> Понятно_Джарвис, что нужно затратив минимальную стоимость срубить последнее (n-е) дерево_Грэхем, т.к. после него все деревья можно будет пилить бесплатно (т.к. c[n] = 0). Посчитаем следующую динамику : dp[i] - минимальная стоимость, заплатив которую будет срублено дерево номер i. Тогда dp[i] = min(dp[j] + a[i] * c[j]) по всем j < i. То есть понятно_Эндрю, что выгодно рубить сначала более дорогие и низкие деревья_Чен, а потом более высокие и дешвые (док-во этого факта оставляется читателям как несложное упражнение). Тогда переберем j < i - индекс предыдущего срубленного дерева. Пусть мы его срубили отптимальным (в смысле денег) способом. Тогда просто a[i_QuickHull|выпуклой оболочки] раз уменьшим высоту дерева i на 1. Каждый такой раз будем платить c[j] за последующую заправку пилы. ИтакПозволяет улучшить асимптотику решения некоторых задач, на сруб i-го дерева мы заплатили a[i]*c[j]. 
Нетрудно видетьрешемых методом динамического программирования, что такая динамика работает за с <math>O(n^2)</math>.==О-Оптимизация== Давайте обозначим dp[j] за b[j], а[i] за x[i], а c[j] за k[j].Теперь формула приняла вид dp[i] = minдо <tex>O(n\cdot\log(k[j]*x[i] + b[j]n)) по всем j < i/tex>. Выражение k[j]*x + b[j] напоминает уравнение прямой y = kx + b. Сопоставим каждому j, обработанному ранее прямую y[j]Техника впервые появилась в 1995 году (xзадачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированию) = k[j]*x + b[j]. Из условия «c[i] убывают <=> k[j] уменьшаются с номером j» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффицента. Давайте нарисуем несколько таких прямых :Массовую известность получила после IOI (рисмеждународной олимпиады по программированию для школьников) 2002.1)

Итак==Пример задачи, решаемой методом convex hull trick==Рассмотрим задачу на ДП:{{Задача|definition = Есть <math>n</math> деревьев с высотами <tex>a_1, a_2, давайте выделим множество точек \dots, a_n</tex> (x0в метрах). Требуется спилить их все, y0) потратив минимальное количество монет на заправкубензопилы. Но пила устроена так, таких что все они принадлежат одной из прямых и при этом нету ни одной прямой y’она может спиливать только по <math>1</math> метру от дерева, к которому ее применили. Также послесрубленного метра (xлюбого дерева)пилу нужно заправлять, такой что y’платя за бензин определенное кол-во монет. Причем стоимость бензина зависит от срубленных (x0полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки равна <tex>c_i</tex>. Изначально пила заправлена.Также известны следующие ограничения : <tex>c_n = 0, a_1 = 1, a_i</tex> возрастают, < y0tex>c_i</tex> убывают. Иными словами возьмем «выпуклую Изначально пила заправлена.(вверхубывание и возрастание нестрогие) оболочку» нашего множества прямых}}(Задача H с Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функциюifmo.ru/school/camp-2016/problems/20160318a. Назовем ее «y pdf Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>)</noinclude><includeonly>{{#if: {{{neat|}}}|<div style="background-color: #fcfcfc; float:left;"><div style="background-color: #ddd;">'''Задача:'''</div><div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div></div>|<table border="0" width="100%"><tr><td style="background-color: #ddd">'''Задача:'''</td></tr><tr><td style= convex(x)» "border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr></table>}}</includeonly>

==Для чего нам нужна Наивное решение==Сначала заметим важный факт : т.к. <tex>c[i]</tex> убывают (нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i]</tex> неотрицательны.Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c[n] = 0</tex>). Посчитаем следующую динамику : <tex>dp[i]</tex> {{---}} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>i</tex> будет срублено.База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна <math>1</math>, по условию задачи.Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта выпуклая оболочка прямых?идея относится скорее к теме [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадных алгоритмов]], чем к теме данной статьи). Поэтому перед <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>-е, причем <tex>j \leqslant i - 1</tex>. Поэтому чтобы найти <tex>dp[i]</tex> нужно перебрать все <tex>1 \leqslant j \leqslant i - 1</tex> и попытаться использовать ответ для дерева номер <tex>j</tex>. Итак, пусть перед <tex>i</tex>-м деревом мы полностью срубили <tex>j</tex>-е, причем высота <tex>i</tex>-го дерева составляет <tex>a[i]</tex>, а т.к. последнее дерево, которое мы срубили, имеет индекс <tex>j</tex>, то стоимость каждого метра <tex>i</tex>-го дерева составит <tex>c[j]</tex>. Поэтому на сруб <tex>i</tex>-го дерева мы потратим <tex>a[i] \cdot c[j]</tex> монет. Также не стоит забывать, что ситуацию, когда <tex>j</tex>-е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет.Итоговая формула пересчета : <tex>dp[i] =\min\limits_{j=1...i-1} (dp[j] + a[i] \cdot c[j])</tex>.

Пусть мы считаем динамику для i-го дерева. Его задает xПосмотрим на код вышеописанного решения: '''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[in]. Итак, нам нужно для данного x'''int''' c[in] найти минимум по всем j k) dp[j1]*x= 0 dp[i2] + b= dp[i3] = y... = dp[jn](x[= <tex>\infty</tex> '''for''' i])= 2 = 1.. Нетрудно видеть, что это есть convex(xn dp[i])= <tex>+\infty</tex> '''for''' j = 1.. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую x = x[i], можно найти бинарным поиском. Это потребует O- 1 '''if''' (logn) времени на поиск такого j, что dp[i] = k[j] * x+ a[i] + b<tex>\cdot</tex> c[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять < dp[i-ю прямую после того, как мы посчитали b]) dp[i] = dp[j] + a[i]. Название статьи подсказывает, что нужно воспользоваться алгоритмом построения выпуклой оболочки множества точек. Но (внезапно) у нас не точки, а прямые… Но что меняется??? Пусть есть 2 стека k<tex>\cdot</tex> c[j] и b '''return''' dp[n], которые задают прямые в отсортированном порядке. Пусть пришла новая прямая. Найдем точки пересечения (по x) с последними 2мя прямыми из стека. Назовем их xL и xR. Если оказалосьНетрудно видеть, что новая прямая пересекает предпосл еднюю прямую выпуклой оболочки позже, чем последнюю (xL такая динамика работает за <tex>= xR), то последнюю можно удалить из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2 или xL не станет меньше xR. Ассимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет O(n^2) суммарно. Корректность : достаточно показать, что прямую нужно удалить из множества т.и т.т., когда она последнюю прямую множества наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем предпоследнюю</tex>.

Теперь формула приняла вид <tex>dp[i] = \min\limits_{j=0...i-1}(рисk[j] \cdot x[i] + b[j])</tex>. Выражение <tex>k[j] \cdot x + b[j]</tex> {{---}} это в точности уравнение прямой вида <tex>y = kx + b</tex>. 2)

Сопоставим каждому <tex>j</tex>, обработанному ранее, прямую <tex>y[j](рисx) = k[j] \cdot x + b[j]</tex>.3)Из условия «<tex>c[i]</tex> убывают <tex>\Leftrightarrow k[j]</tex> уменьшаются с номером <tex>j</tex>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :

ДействительноВыделим множество точек <tex>(x_0, пусть новая прямая пересекает последнюю прямую множества позжеy_0)</tex> , чем предпоследнюю таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняяx)</tex>, то найдется такой отрезок [x1;x2]что <tex>y’(x_0) < y_0</tex>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней огибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что последняямножество точек <math>(желтаяx, convex(x)) прямая при этих x-ах лежит ниже всех остальных и ее следует оставить в множестве</math> представляет собой выпуклую вверх функцию.

==Цель нижней огибающей множества прямых==Пусть мы считаем динамику для <tex>i</tex>-го дерева. Его задает <tex>x[i]</tex>. Итак, нам нужно для данного <tex>x[i]</tex> найти <tex>\min\limits_{j=0..i-1}(k[j] \cdot x[i] + b[j]) = \min\limits_{j=0..i-1}(y[j](x[i]))</tex>. Это выражение есть <math>convex(x[i])</math>. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координатам x следует то, что отрезок, который пересекает прямую <tex>x = x[i]</tex>, можно найти [[Целочисленный_двоичный_поиск|бинарным поиском]]. Это потребует <tex>O(\log(n))</tex> времени на поиск такого <tex>j</tex>, что <tex>dp[i] = k[j] \cdot x[i] + b[j]</tex>. Теперь пусть осталось научиться поддерживать множество прямых и быстро добавлять <tex>i</tex>-ю прямую после того, как мы посчитали <tex>b[i] = dp[i]</tex>. Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека <tex>k[]</tex> и <tex>b[]</tex>, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую (<tex>i</tex>-тую) прямую в множество. Пусть сейчас в множестве лежит <tex>sz</tex> прямых (нумерация с 1). Пусть <tex>(x_L, y_L)</tex> {{---}} точка пересечения <tex>sz - 1</tex>-й прямой множества и <tex>sz</tex>-й, а <tex>(x_R, y_R)</tex> {{---}} точка пересечения новой прямой, которую мы хотим добавить в конец множества и <tex>sz</tex>-й. Нас будут интересовать только их <tex>x</tex>-овые координаты <tex>x_L</tex> и <tex>x_R</tex>, соответственно. Если оказалось, что новая прямая пересекает <tex>sz</tex>-ю прямую выпуклой оболочки позже, чем <tex>sz</tex>-я <tex>sz - 1</tex>-ю, т.е. <tex>(x_L \geqslant x_R)</tex>, то <tex>sz</tex>-ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо число прямых в стеке не станет равным 2, либо <tex>x_L</tex> не станет меньше <tex>x_R.</tex> Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1</math> раз добавится в стек и максимум <math>1</math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно. [[Файл:picture2convexhull.png]][[Файл:picture3convexhull.png]] {{Теорема|id=th1239. |statement=Алгоритм построения нижней огибающей множества прямых корректен.|proof=Достаточно показать, что последнюю прямую нужно удалить из множества раньше<tex>\Leftrightarrow</tex>, когда наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю . Пусть <tex>Y(x) = Kx + B</tex> {{---}} уравнение новой прямой, <tex>y[i](x) = K[i]x + B[i]</tex> {{---}} уравнения прямых множества. Тогда т.к. <tex>K < K[sz]</tex>, то при <tex>x \in [- \infty; x_R] : y[sz](x) <= Y(рисx)</tex>, а т.к.<tex> K[sz] < K[sz - 1]</tex>, то при <tex>x \in [x_L; + \infty] : y[sz - 1](x) \geqslant y[sz](x)</tex>. Если <tex>x_L < x_R</tex>, то при <tex>x \in [x_L; x_R] последняя : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)</tex>, т.е. на отрезке <tex>[x_L; x_R]</tex> прямая при любых x номер sz лежит выше какой-ниже остальных и её нужно оставить в множестве. Если же <tex>x_L > x_R</tex>, то другой прямой множества и значит ее она ниже всех на отрезке <tex>[x_L; x_R] = \varnothing </tex>, т.е. её можно удалить, чтдиз множества.}}

Будем хранить 2 массива : <tex>front[]</tex> {{---}} <tex>x</tex>-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (имитирующих стеки) : т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при <tex>x</tex> <tex>\in</tex> <tex>[front[i]; front[i + 1] )</tex> ) и <tex>st[] </tex> {{--- начало }} номера деревьев, соответствующих прямым (по x) соответствующей прямой выпуклой оболочки и т.е. <tex>i</tex>-я прямая множества, где <tex>i</tex> <tex>\in</tex> <tex>[1; sz]</tex> соответствует дереву номер этой прямой (в глобальной нумерации<tex>sz[i]</tex>). Также воспользуемся тем, что <tex>x[i] = a[i] </tex> возрастают (по условию задачи), а значит мы можем искать первое такое <tex>j</tex>, что <tex>x[i] >= \geqslant front[j] </tex> не бинарным поиском, а методом 2х двух указателей за <tex>O(n) </tex> операций суммарно. Также массив <math>front[] </math> можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси xдо ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые <tex>x[i]</tex>, а значит если <tex>k</tex>-я прямая пересекается с <tex>k+1</tex>-й в точке <tex>z +</tex> <tex>\alpha</tex> (<math>z</math>-целое, <tex>\alpha</tex> <tex>\in</tex> <tex>[0;1)</tex>), то мы будем подставлять в их уравнения <tex>z</tex> или <tex>z + 1</tex>. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с <tex>x = z+1</tex> ==Реализация== '''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n]) st[1] = 1 front[1] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font> sz = 1 <font color=green>// текущий размер выпуклой оболочки </font> pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] </font > '''for''' i = 2..n '''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font > pos = pos + 1 j = st[pos] dp[i] = K[j] <math>\cdot</math> a[i] + B[j] '''if''' (i < n) <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font > K[i] = c[i] <font color=green>// наши переобозначения переменных </font > B[i] = dp[i] <font color=green>// наши переобозначения переменных </font > x = -<tex>\infty</tex> '''while''' ''true'' j = st[sz] x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font > '''if''' (x > from[sz]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font > sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font > st[sz + 1] = i front[sz + 1] = x <font color=green>// добавили новую прямую </font > sz = sz + 1 '''return''' dp[n] Здесь функция <tex>\mathtt{divide(a, b)}</tex> возвращает нужное(*) округление <tex>\frac{a}{b}</tex>. Приведем её код : '''int''' <tex>\mathtt{divide}</tex>('''int''' a, '''int''' b) delta = 0 '''if''' (a '''mod''' b ≠ 0) delta = 1 '''if''' ((a > 0 '''and''' b > 0) '''or''' (a < 0 '''and''' b < 0)) '''return''' [a / b] + delta '''return''' -[|a| / |b|]  Такая реализация будет работать за <math>O(n)</math>. ==Динамический convex hull trick== Заметим, что условия на возрастание/убывание <tex>k[i]</tex> на убывание/возрастание и <tex>x[i]</tex> выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>).

==Р.РеализацияАльтернативный подход == st[0] = 0 from[0] = -∞ sz = 1 // текущий размер выпуклой оболочки pos = 0 // текущая позиция первго такого j, что xДругой способ интерпретировать выражение <tex>dp[i] >= front[st[\min\limits_{j]] for i = 10...ni-1 while }(frontc[posj] < x\cdot a[i]) ++pos dp[j = st])</tex> заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : <tex>dp[posj] dp+ a[i] = K\cdot c[j] * a= (dp[ij] + B, c[j] if ) \cdot (1, a[i ])< n - 1) // если у нас добавляется НЕ последняя прямаяtex>, Kт.е. запишем как скалярное произведение векторов <tex>v[ij] = b(dp[ij] B, c[ij] = dp)</tex> и <tex >u[i] ll x = -inf while (1, a[i]) </tex >. Вектора <tex >v[j ] = st (dp[sz - 1j], c[j] x = divide)</tex> хотелось бы организовать так, чтобы за <tex >O(\log(Bn))</tex> находить вектор, максимизирующий выражение <tex>v[j] - B\cdot u[i], K</tex>. Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) <tex>j</tex> не может давать более оптимальное значение <tex>v[j] \cdot u[i] - K</tex> одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов <tex>v[j]) if (x </tex> from[sz , а ответ на запрос {{- 1]) break --sz st}} это поиск <tex>v[szj] = </tex>, максимизирующего проекцию на <tex>u[i from[sz++] = x </tex>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (Здесь функция divideиз <tex>(a0, b0) возвращает нужное округление </tex> в <tex>(1, a [i])</tex>). Ее можно решить за <tex>O(\log(n))</ btex> двумя бинарными или одним тернарным поискомАсимптотика алгоритма по-прежнему составит <tex>O(n \cdot \log(n))</tex>

Такая реализация будет работать за O(n)[[Файл:picture5convexhull.png]]

Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются <math>3</math> вектора <math>a, b, c</math>, расположенные как на рис. 5, т.е. точка <math>b</math> не лежит на выпуклой оболочке векторов <tex>0, a, b, c </tex> : <tex> \Leftrightarrow [a-b, b-c] < 0 </tex>, то либо <tex>(a, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>, либо <tex>(c, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>.{{Теорема|id=th12392. |statement=Динамический convex hull trickЕсли есть <tex>3</tex> вектора <tex>a, b, c</tex>, таких что <tex>[a-b, b-c] < 0</tex> то либо <math>(a, u) < (b, u)</math>, либо <math>(c, u) < (b, u)</math>, где вектор <math>u =(1; k)</math>.|proof=По условию теоремы известно, что <tex>[a-b, b-c] < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u) < (a, u) \Leftrightarrow b_{x} + k \cdot b_{y} < a_{x} + k \cdot a_{y} \Leftrightarrow (b_{x} - a_{x}) < k \cdot (a_{y} - b_{y})</tex> и при этом <tex>(b, u) < (c, u) \Leftrightarrow b_{x} + k \cdot b_{y} < c_{x} + k \cdot c_{y} \Leftrightarrow (c_{x} - b_{x}) > k \cdot (b_{y} - c_{y})</tex>.

Заметим, что условия на прямые, что Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = k[i] возрастает</убывает и x[i] убываетtex><tex> \cdot (b_{y} - a_{y}) \cdot </возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи tex><tex>(пример : задача G отсюда http:b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</neerc.ifmo.rutex><tex> \cdot (b_{y} - c_{y})</schooltex><tex> < (a_{y} - b_{y}) \cdot </camptex><tex>(b_{x} -2016c_{x})</problemstex> <tex>< k \cdot (a_{y} - b_{y})</20160318a.pdftex><tex> \cdot (c_{y} - b_{y})</tex>. Но рассмотрим общий случай. Наша задача поменялась следующим образом Получили противоречие : по<tex>k \cdot (a_{y} -прежнему у нас есть выпуклая оболочка, имея которую мы за Ob_{y}) \cdot (lognc_{y} - b_{y}) или быстрее можем найти dp[i], но теперь вставку i< k \cdot (a_{y} -й прямой в оболочку уже нельзя выполнить старым способом за O(1b_{y}) \cdot (в среднемc_{y} - b_{y})</tex>. У нас есть выпуклая оболочкаЗначит предположение неверно, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине чтд.(рис. 4). }}

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

Другой способ интерпретировать выражение dp[i] = max(dp[j] + a[i] * c[j]) по всем их заключается в следующем: давайте перепишем выражение dp[j] + a[i] * c[j] = (dp[j], c[j]) * (1, a[i]), т.е. запишем ка скалярное произведение векторов v[j] = (dp[j], c[j]) и u[i] = (1, a[i]). Вектора v[j] = (dp[j], c[j]) хотелось бы организовать так, чтобы за O(logn) находить максимизирующий выражение v[j] * u[i]. Посмотрим на рис. 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) двумя бинарными или одним тернарным поиском