Dynamic Upper Envelope of lines in the plane
"someone" is right.  Timothy Chan's paper "Dynamic Planar Convex Hull Operations in
Near-Logarithmic Amortized Time" appears to solve the problem with insertions/deletions taking $O(\log ^{1+\epsilon}n)$ amortized time, and queries taking $O(\log n)$ time.  He solves your problem which is dual to the convex hull problem.