Изменения
→Для чего нам нужна эта выпуклая оболочка прямых?
Итак, давайте выделим множество точек (x0, y0) , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой y’(x), такой что y’(x0) < y0. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «y = convex(x)»
==Для чего нам нужна эта выпуклая оболочка прямых?==
Пусть мы считаем динамику для <math>i</math>-го дерева. Его задает <math>x[i]</math>. Итак, нам нужно для данного <math>x[i] </math> найти минимум по всем <math>min_{j =0..i-1}(k[j]*x[i] + b[i] ) = min_{j=0..i-1}(y[j](x[i]))</math>. Нетрудно видеть, что это есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую <math>x = x[i]</math>, можно найти бинарным поиском. Это потребует O(logn) времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять <math>i</math>-ю прямую после того, как мы посчитали <math>b[i] = dp[i]</math>. Название статьи подсказывает, что нужно воспользоваться алгоритмом построения выпуклой оболочки множества точек. Но (внезапно) у нас не точки, а прямые… Но что меняется??? Пусть есть 2 стека <math>k[] и b[]</math>, которые задают прямые в отсортированном порядке. Пусть пришла новая прямая. Найдем точки пересечения (по x) с последними 2мя прямыми из стека. Назовем их <math>xL </math> и <math>xR</math>. Если оказалось, что новая прямая пересекает предпосл еднюю прямую выпуклой оболочки позже, чем последнюю (xL >= xR), то последнюю можно удалить из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2 или <math>xL </math> не станет меньше <math>xR.</math> Ассимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет <math>O(n) </math> суммарно.
Корректность : достаточно показать, что прямую нужно удалить из множества т.и т.т., когда она последнюю прямую множества наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем предпоследнюю.
Действительно, пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), то найдется такой отрезок <math>[x1;x2]</math>, что последняя(желтая) прямая при этих x-ах лежит ниже всех остальных и ее следует оставить в множестве.
Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.
==Детали реализации:==
Будем хранить 2 массива (имитирующих стеки) : <math>front[]</math> и <math>st[]</math> - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что <math>x[i] = a[i]</math> возрастают (по условию задачи), а значит мы можем искать первое такое <math>j</math>, что <math>x[i] >= front[j]</math> не бинарным поиском, а методом 2х указателей за <math>O(n)</math> суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x.
