Изменения
→Реализация
==Реализация==
'''void''' Convex-hull-trick
st[01] = 01 from[01] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font>
sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
pos = 0 1 <font color=green>// текущая позиция первого такого j, что x[i] >= front[st[j]] </font > '''for''' i = 12..n-1 {
'''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >
pos = pos ++pos1
j = st[pos]
dp[i] = K[j] * a[i] + B[j]
'''if''' (i < n - 1) { <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
K[i] = c[i] <font color=green>// наши переобозначения переменных </font >
'''while''' (true) {
j = st[sz - 1] x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font > '''if ''' (x > from[sz - 1]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font > sz = sz --sz 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
}
st[sz+ 1] = i from[sz++1] = x <font color=green>// добавили новую прямую </font > sz = sz + 1
}
}
