Store lines in a deque (double-ended queue), ordered by slope. The front has the smallest slope (optimal for small ). The back has the largest slope (optimal for large ). For queries: check if the second line beats the first at current .
If yes, pop the front. Repeat until the front is optimal. For insertions: add new lines at the back. But first, remove lines that become dominated. Both operations are amortized because each line enters and leaves at most once.