Let's say I have a set of lines, y = ax+b and three types of online queries:
- Given a and b, insert the line.
- Given a and b, delete the line (it is assured that the line exists)
- Given x0, print the maximum possible value of y.
(a is distinct for all the lines, a & b are integers.)
number of lines <= 1e5.
number of queries <= 3e5.
So O(log n / log^2 n / sqrt n) should work, according to me.
Can anyone help me with this?