First of all, let’s find out how the length of a queue depends on time. That is, we need to solve the differential equation
with an initial condition l(t0)=l0 if the queue’s parameters were last updated at time t0. Simple rearranging and integration gives (l2 − l02)/2 = g(t − t0), so $l=\sqrt{l_0^2+2g(t-t_0)}$ and
There are two main observations to be made here:
The first observation is true because τi is just a square root of a linear function, the second one holds thanks to non-decreasing vi and non-increasing gi. What do they tell us? Thanks to the first one, if we know that one function became smaller than another after some time, we can discard the latter; this allows us to construct an algorithm where we maintain a set of “interesting” functions with the only operations being “move forward in time” and “add a function”. The second observation lets us keep old functions without removing them (they can stop being interesting, though), since that doesn’t decrease the minimum, so we can treat U-queries as O-queries.
In the easy subproblem, we can compute time intervals when each function gives the minimum. Let’s sort the functions non-increasingly by their values at an infinite time - by $\sqrt{g_i}/v_i$. We’ll push them into a stack in that order. Before pushing in a function f, we can remove all functions at the top of the stack which are never smaller than f - those which can become minimum (either at time 0 when they’re added or when they intersect with a previously added function) only after intersecting with f. Afterwards, only the last function before f in the stack determines when f can become minimum and we can compute their intersection point (if it exists).
For each function that’s left in the stack at the end, we now have a non-empty interval when it’s minimum. Answering a type Q query is just a matter of finding the right time interval. Overall, this takes O((M + Q)logM) time. Note the similarity to the convex hull algorithm; in fact, the full solution in case the functions are linear and not sqrt(linear) is known under the name “convex hull trick”.
With U/O queries, we can still parse the input, find all functions with times when they’re added and sort everything by $v_i/\sqrt{g_i}$. We’ll keep a set of interesting functions (those which can yet become minimum - haven’t been intersected by an added function that comes later in the sort order) and a priority queue of events - intersections between them, sorted by time. We don’t need to keep track of all intersections, only those between functions adjacent in the sort order; this way, each function has to gradually intersect all those before it to become the minimum.
There are two types of operations to implement: add a function and process events occurring before a given time. When adding a function, we should look at its nearest ≤2 interesting neighbours and add corresponding two events; when removing a function (making it non-interesting) with 2 neighbours, we should add one event between them. When processing an event, we need to check if it’s still valid, since one of the functions between which it would’ve happened could have been removed, and if it is, remove the function earlier in the sort order. Afterwards, the first interesting function gives the minimum at the given time.
Since we only add 1 event when removing a function and 2 when adding it, there can only be O(M + Q) events to process. Processing one takes O(logM + Q) time, so the time complexity of the full algorithm is still just O((M + Q)logM + Q).