Think about the problem this way: You are managing a collection of piecewise linear functions fi(x) = ai x + bi (li <= x <= ri) subject to the following operations:
- Add a new function
- Find the maximum of all the functions added so far that are defined for a specific value of x
I see two possible approaches:
- Store only the maximum ("upper hull") of all the functions, which is in turn a collection of piecewise linear functions, but with disjoint definition intervals. UPDATE: I initially thought this could be done with a simple binary search tree, but it's not as simple as that, so I would go with option 2
- Follow a more standard approach and use a segment tree on the x range (the "array"), that stores sets of linear functions in its nodes. Now for a given x, you can walk up the tree to find out what linear functions are defined at that point and use the standard convex hull trick to find their maximum at x. Complexity: O(n + M * log n * log M)