Section Recap

You've learned the Convex Hull Trick:

$1.$ When DP has linear terms mixing indices, rewrite as $\min_j(m_j \cdot x_i + c_j)$.

$2.$ Each $j$ defines a line. You query the lower envelope at $x_i$.

$3.$ For sorted queries: $O(n)$ total using a deque.

$4.$ For arbitrary queries: $O(n \log n)$ using binary search or Li Chao tree. CHT doesn't need QI. It works on a completely different structure: linearity. You now have another tool for breaking through TLE. For practice, solve the problems in the problemset.