Convex Hull Trick: когда ДП-переход можно ускорить и как это понять?

CHT применим, когда переход имеет вид dp[i] = min_{j<i} ( dp[j] + b[j] · x[i] ) (или max), то есть для каждого i ты минимизируешь по j линейную функцию от x[i] с коэффициентом b[j]. Каждое предыдущее состояние j задаёт прямую y = b[j]·x + dp[j]. Найти минимум по всем прямым в точке x[i] — это запрос к нижней огибающей набора прямых. Наивно это O(n) на запрос → O(n²) всего. CHT хранит огибающую и отвечает за O(1) амортизированно (или O(log n)), убирая лишние прямые.

Идея «почему линейно»: оптимальная прямая в нижней огибающей выпукла, и если запросы x[i] монотонны, то указатель оптимума движется только в одну сторону. Добавление прямой и поиск — амортизированно O(1).

// нижняя огибающая для min, x монотонно растут
struct Line { long long k, b; long long eval(long long x){ return k*x + b; } };
vector<Line> hull; int ptr = 0;
bool bad(Line l1, Line l2, Line l3) { // l2 не нужна?
    return (__int128)(l3.b - l1.b) * (l1.k - l2.k)
         <= (__int128)(l2.b - l1.b) * (l1.k - l3.k);
}
void add(long long k, long long b) {           // k убывает
    Line l{k, b};
    while (hull.size() >= 2 && bad(hull[hull.size()-2], hull.back(), l)) hull.pop_back();
    hull.push_back(l);
}
long long query(long long x) {                 // x возрастает
    if (ptr >= (int)hull.size()) ptr = hull.size()-1;
    while (ptr + 1 < (int)hull.size() && hull[ptr+1].eval(x) <= hull[ptr].eval(x)) ptr++;
    return hull[ptr].eval(x);
}

Сложность O(n) при монотонных наклонах и запросах. Грабля: пересечения считай в __int128, иначе переполнение в bad() даст неверную огибающую и WA. Если монотонности нет — бери Li Chao tree или CHT с бинпоиском за O(n log n).