Hi, as far as I know, the O(1) convex hull trick (using either vector or deque) requires the lines to be inserted in strictly increasing gradients.
However is there a condition that must be satisfied for x in the query part? I have always previously thought for a maximum finding convex hull, x must be queried in increasing order, however there was one question which i managed to AC by ignoring the fact that x in the query must be increasing. So was the TCs weak? or was what I had previously thought wrong lol?
Btw what i did in the question: sort the lines by increasing m, where i'll set m to be the gradient of the line which I'll insert, and do query(-2*m) (Maybe it's something to do with the negative? I'm not too sure)
Thanks in advance.
You calling a function called "query" says nothing without a concrete implementation.
The monotone gradients are required for building the whole thing in $$$O(N)$$$, which is amortized $$$O(1)$$$ per line added.
The query part requires binary search and is $$$O(logN)$$$, but can be optimized to $$$O(1)$$$ by walking a pointer if all your queries are in monotone order.
My guess is that whatever implementation you used was $$$O(log)$$$ per query and didn't require ordered queries, as I can't see how a pointer-based one would handle non-monotone queries at all.