### The problem

Let us consider the problem where we need to quickly calculate the following over some set *S* of *j* for some value *x*.

Additionally, insertion of new *j* into *S* must also be efficient.

This will most likely be encountered with DP problems. For example, the recent problem 1083E - The Fair Nut and Rectangles from Round #526 has the following DP formulation after sorting the rectangles by *x*.

*f*(

*i*) =

*x*

_{i}·

*y*

_{i}-

*a*

_{i}+

*max*

_{1 ≤ j < i}{ -

*x*

_{j}·

*y*

_{i}+

*f*(

*j*)}

The problem requires quick calculation of the above define maximum for each index *i*. How can this be done?

### The idea

Notice the special form of *m*_{j}·*x* + *c*_{j}. This is identical to the equation of a straight line with slope *m*_{j} and Y-intercept *c*_{j}. So the problem is equivalent to being given a set of lines and asked for the maximum *y* value any of those lines can give at a particular *x*. If you draw a bunch of straight lines on a plane, you'll notice that the maximum values are along what appears to be a convex hull.

Some observations:

- Every line on the hull provides the maximum value on some contiguous range of
*x*values. Conversely, every line not on the hull is useless and never provides the maximum. - All the lines on the hull have different slopes. The order of slopes also determines their position on the hull. A line with lower slope appears on the hull to the left of one with a higher slope.

So, a possible strategy can be to only maintain the convex hull and not keep the useless lines