Hi. I recently overcomplicated one easy-ish geometry problem and encountered the following difficulty.

Let's say I have a set of linear functions *f*(*x*) = *ax* + *b* and two types of online queries:

- Given
*a*and*b*, insert a new linear function. - Given
*x*_{0}, print the maximum value*f*(*x*_{0}).

I can handle both queries in logarithmic time by using BST and maintaining the convex hull of linear functions. Can I do the same (easily?) using `set`

in C++? The problem is that the second query requires `lower_bound`

that is able to say whether a linear function is on the left or on the right from the optimal one. I think it's impossible because it depends on the neighboring (after sorting CH by slope) functions.

During a contest, I implemented something in *O*(*log*^{2}) — a lower_bound that runs an internal lower_bound to find the next linear function in the set. Later I came up with an idea to extend a linear-function struct to also store a copy of the next function in the set. It requires some extra work but should work and should be *O*(*log*), right? Do you see any easier way?