Convex hull trick — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Convex hull trick Постановка примера задачи: Есть n деревьев с высотами a1, a2, … an. Требуется спили...»)
 
Строка 1: Строка 1:
Convex hull trick
+
==Постановка примера задачи:==
Постановка примера задачи:
 
 
Есть n деревьев с высотами a1, a2, … an. Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так, что после уменьшения высоты спиливаемого дерева на 1 ее надо заправить. Причем стоимость заправки зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки равна ci.  Изначально пила заправлена.
 
Есть n деревьев с высотами a1, a2, … an. Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так, что после уменьшения высоты спиливаемого дерева на 1 ее надо заправить. Причем стоимость заправки зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки равна ci.  Изначально пила заправлена.
 
И известны следующие ограничения : c[n] = 0, a[1] = 1, a[i] возрастают, c[i] убывают.
 
И известны следующие ограничения : c[n] = 0, a[1] = 1, a[i] возрастают, c[i] убывают.
(Задача с codeforces.com)
+
(Задача с [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] раз уменьшим высоту дерева i на 1. Каждый такой раз будем платить c[j] за последующую заправку пилы. Итак, на сруб i-го дерева мы заплатили a[i]*c[j]. 
Нетрудно видеть, что такая динамика работает за <math>O(n^2)</math>.
Понятно, что нужно затратив минимальную стоимость срубить последнее (n-е) дерево, т.к. после него все деревья можно будет пилить бесплатно (т.к. c[n] = 0). Посчитаем следующую динамику : dp[i] - минимальная стоимость, заплатив которую будет срублено дерево номер i. Тогда dp[i] = min(dp[j] + a[i] * c[j]) по всем j < i. То есть понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешвые (док-во этого факта оставляется читателям как несложное упражнение). Тогда переберем j < i - индекс предыдущего срубленного дерева. Пусть мы его срубили отптимальным (в смысле денег) способом. Тогда просто a[i] раз уменьшим высоту дерева i на 1. Каждый такой раз будем платить c[j] за последующую заправку пилы. Итак, на сруб i-го дерева мы заплатили a[i]*c[j]. 
Нетрудно видеть, что такая динамика работает за O(n^2).
+
==О-Оптимизация==
 
О-Оптимизация
 
 
Давайте обозначим dp[j] за b[j], а[i] за x[i], а c[j] за k[j].
 
Давайте обозначим dp[j] за b[j], а[i] за x[i], а c[j] за k[j].
 
Теперь формула приняла вид dp[i] = min(k[j]*x[i] + b[j]) по всем j < i. Выражение k[j]*x + b[j] напоминает уравнение прямой y = kx + b. Сопоставим каждому j, обработанному ранее прямую y[j](x) = k[j]*x + b[j]. Из условия «c[i] убывают <=>  k[j] уменьшаются с номером j» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффицента. Давайте нарисуем несколько таких прямых :
 
Теперь формула приняла вид dp[i] = min(k[j]*x[i] + b[j]) по всем j < i. Выражение k[j]*x + b[j] напоминает уравнение прямой y = kx + b. Сопоставим каждому j, обработанному ранее прямую y[j](x) = k[j]*x + b[j]. Из условия «c[i] убывают <=>  k[j] уменьшаются с номером j» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффицента. Давайте нарисуем несколько таких прямых :
 
+
(рис.1)
 
 
  
 
Итак, давайте выделим множество точек (x0, y0) , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой y’(x), такой что y’(x0) < y0. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «y = convex(x)»  
 
Итак, давайте выделим множество точек (x0, y0) , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой y’(x), такой что y’(x0) < y0. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «y = convex(x)»  
  
 
+
==Для чего нам нужна эта выпуклая оболочка прямых?==
 
 
 
 
 
 
(рисунок 1)
 
 
 
 
 
Для чего нам нужна эта выпуклая оболочка прямых?
 
  
 
Пусть мы считаем динамику для i-го дерева. Его задает x[i]. Итак, нам нужно для данного x[i] найти минимум по всем j k[j]*x[i] + b[i] = y[j](x[i]). Нетрудно видеть, что это есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую x = x[i], можно найти бинарным поиском. Это потребует O(logn) времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять i-ю прямую после того, как мы посчитали b[i] = dp[i].  
 
Пусть мы считаем динамику для i-го дерева. Его задает x[i]. Итак, нам нужно для данного x[i] найти минимум по всем j k[j]*x[i] + b[i] = y[j](x[i]). Нетрудно видеть, что это есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую x = x[i], можно найти бинарным поиском. Это потребует O(logn) времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять i-ю прямую после того, как мы посчитали b[i] = dp[i].  
Строка 31: Строка 20:
  
  
 +
(рис. 2)
  
 
+
(рис.3)
 
 
 
 
 
 
(рис. 2) (рис. 3)
 
  
  
Строка 43: Строка 29:
 
Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1),  последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.
 
Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1),  последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.
  
Детали реализации:
+
==Детали реализации:==
 
Будем хранить 2 массива (имитирующих стеки) : front[] и st[] - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что x[i] = a[i] возрастают (по условию задачи), а значит мы можем искать первое такое j, что x[i] >= front[j] не бинарным поиском, а методом 2х указателей за O(n) суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x.
 
Будем хранить 2 массива (имитирующих стеки) : front[] и st[] - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что x[i] = a[i] возрастают (по условию задачи), а значит мы можем искать первое такое j, что x[i] >= front[j] не бинарным поиском, а методом 2х указателей за O(n) суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x.
  
  
  
Р.Реализация
+
==Р.Реализация==
 
+
            st[0] = 0
st[0] = 0
+
            from[0] = -∞
from[0] = -∞
+
            sz = 1 // текущий размер выпуклой оболочки
sz = 1 // текущий размер выпуклой оболочки
+
            pos = 0 // текущая позиция первго такого j, что x[i] >= front[st[j]]
pos = 0 // текущая позиция первго такого j, что x[i] >= front[st[j]]
+
            for  i = 1..n-1
for  i = 1..n-1
+
            while (front[pos] < x[i]) ++pos
while (front[pos] < x[i]) ++pos
+
                    j = st[pos]
      j = st[pos]
+
                    dp[i] = K[j] * a[i] + B[j]
        dp[i] = K[j] * a[i] + B[j]
+
                    if (i < n - 1)  // если у нас добавляется НЕ последняя прямая,  
        if (i < n - 1)  // если у нас добавляется НЕ последняя прямая,  
+
                        K[i] = b[i]
          K[i] = b[i]
+
            B[i] = dp[i]
B[i] = dp[i]
+
                        ll x = -inf
            ll x = -inf
+
                        while (1)
            while (1)
+
                          j = st[sz - 1]
            j = st[sz - 1]
+
                            x = divide(B[j] - B[i], K[i] - K[j])
              x = divide(B[j] - B[i], K[i] - K[j])
+
                          if (x > from[sz - 1]) break
              if (x > from[sz - 1]) break
+
                            --sz
              --sz
+
                        st[sz] = i
          st[sz] = i
+
                        from[sz++] = x
          from[sz++] = x
 
 
    
 
    
 
(Здесь функция divide(a, b) возвращает нужное округление a / b)
 
(Здесь функция divide(a, b) возвращает нужное округление a / b)
Строка 74: Строка 59:
 
Такая реализация будет работать за O(n).
 
Такая реализация будет работать за O(n).
  
Динамический convex hull trick
+
==Динамический convex hull trick==
  
 
Заметим, что условия на прямые, что k[i] возрастает/убывает и x[i] убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).
 
Заметим, что условия на прямые, что k[i] возрастает/убывает и x[i] убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).
Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за O(logn) или быстрее можем найти dp[i], но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за O(1) (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине (рис. 4).  
+
Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за O(logn) или быстрее можем найти dp[i], но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за O(1) (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине  
 +
(рис. 4).  
  
 
Т.е. нужно уметь быстро (за O(logn)?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) примую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить std::set (или любой аналог в других языках) пар <k, st> =  <коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей.
 
Т.е. нужно уметь быстро (за O(logn)?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) примую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить std::set (или любой аналог в других языках) пар <k, st> =  <коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей.
 
Ассимптотика решения составит O(logn) на каждый из n запросов «добавить прямую» + O(n) суммарно на удаление прямых. Итго O(nlogn).
 
Ассимптотика решения составит 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) двумя бинарными или одним тернарным поиском
 
Другой способ интерпретировать выражение 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) двумя бинарными или одним тернарным поиском
  
  
 
Ассимптотика алгоритма по-прежнему составит O(nlogn)
 
Ассимптотика алгоритма по-прежнему составит O(nlogn)

Версия 18:42, 23 ноября 2016

Постановка примера задачи:

Есть n деревьев с высотами a1, a2, … an. Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так, что после уменьшения высоты спиливаемого дерева на 1 ее надо заправить. Причем стоимость заправки зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки равна ci. Изначально пила заправлена. И известны следующие ограничения : c[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] раз уменьшим высоту дерева 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(k[j]*x[i] + b[j]) по всем j < i. Выражение k[j]*x + b[j] напоминает уравнение прямой y = kx + b. Сопоставим каждому j, обработанному ранее прямую y[j](x) = k[j]*x + b[j]. Из условия «c[i] убывают <=> k[j] уменьшаются с номером j» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффицента. Давайте нарисуем несколько таких прямых : (рис.1)

Итак, давайте выделим множество точек (x0, y0) , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой y’(x), такой что y’(x0) < y0. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «y = convex(x)»

Для чего нам нужна эта выпуклая оболочка прямых?

Пусть мы считаем динамику для i-го дерева. Его задает x[i]. Итак, нам нужно для данного x[i] найти минимум по всем j k[j]*x[i] + b[i] = y[j](x[i]). Нетрудно видеть, что это есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую x = x[i], можно найти бинарным поиском. Это потребует O(logn) времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять i-ю прямую после того, как мы посчитали b[i] = dp[i]. Название статьи подсказывает, что нужно воспользоваться алгоритмом построения выпуклой оболочки множества точек. Но (внезапно) у нас не точки, а прямые… Но что меняется??? Пусть есть 2 стека k[] и b[], которые задают прямые в отсортированном порядке. Пусть пришла новая прямая. Найдем точки пересечения (по x) с последними 2мя прямыми из стека. Назовем их xL и xR. Если оказалось, что новая прямая пересекает предпосл еднюю прямую выпуклой оболочки позже, чем последнюю (xL >= xR), то последнюю можно удалить из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2 или xL не станет меньше xR. Ассимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет O(n) суммарно. Корректность : достаточно показать, что прямую нужно удалить из множества т.и т.т., когда она последнюю прямую множества наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем предпоследнюю.


(рис. 2)

(рис.3)


Действительно, пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), то найдется такой отрезок [x1;x2], что последняя(желтая) прямая при этих x-ах лежит ниже всех остальных и ее следует оставить в множестве.

Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.

Детали реализации:

Будем хранить 2 массива (имитирующих стеки) : front[] и st[] - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что x[i] = a[i] возрастают (по условию задачи), а значит мы можем искать первое такое j, что x[i] >= front[j] не бинарным поиском, а методом 2х указателей за O(n) суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x.


Р.Реализация

            st[0] = 0
            from[0] = -∞
            sz = 1 // текущий размер выпуклой оболочки
            pos = 0 // текущая позиция первго такого j, что x[i] >= front[st[j]]
            for  i = 1..n-1

while (front[pos] < x[i]) ++pos

                   	j = st[pos]
                    	dp[i] = K[j] * a[i] + B[j]
                    	if (i < n - 1)  // если у нас добавляется НЕ последняя прямая, 
                       		K[i] = b[i]

B[i] = dp[i]

                        	ll x = -inf
                        	while (1)	
            		              j = st[sz - 1]
              		              x = divide(B[j] - B[i], K[i] - K[j])
            	 	               if (x > from[sz - 1]) break
              	              	--sz
                       st[sz] = i
                       from[sz++] = x
 

(Здесь функция divide(a, b) возвращает нужное округление a / b)

Такая реализация будет работать за O(n).

Динамический convex hull trick

Заметим, что условия на прямые, что k[i] возрастает/убывает и x[i] убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf). Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за O(logn) или быстрее можем найти dp[i], но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за O(1) (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине (рис. 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) двумя бинарными или одним тернарным поиском


Ассимптотика алгоритма по-прежнему составит O(nlogn)