dynamic convex hull of lines
There are n persons taking part in a race. They all start at position x = 0 with initial velocity zero.
You are Q queries to support, each of which could be one of the following:
- Change the speed of i-th person to v_i at some T.
- Ask the position of the leader at some time t.
- Time values are distinct and are sorted in increasing order w.r.t queries.
- Speed of a cyclist can not decrease.
If position of a person is x and speed is v, then at time t, his position will be x + v * t.
Now, assume that we change its speed at time T from v to v'.
Now position of the person at time t > T, will be x + v * T + v' * (t - T) = (x + (v - v') * T) + v' * t
i.e. x' + v' t where x' = (x + (v - v') * T).
So, the information that we need to store for a cyclist is values (x, v) for it, such that x + v * t will give its position at a time t.
Using the above equations, we also know how to update this information for the update query (i.e. query of type 2) : Change x to x' and v to v'.
Now, we know the information (x_i, v_i) for each person, we want to know the position of leader at time t.
The trivial O(n) solution will be to iterate over all the racers and find the maximum of (x_i + v_i * t). This solution is enough to solve the first subtask.
We want to find something better.
Let us plot position of a person vs time (t). We know that position of a person at time will be given by equation x + v * t, which is a straight line passing throught (0, x) and has positive slope of v.
Let us plot all these lines for each person in 2D plane. We can note that the curve corresponding to position of leader at various times will be lower convex hull of all these lines.
We can maintain this lower hull by maintaining the order of lines appearing in the hull w.r.t. increasing t coordinate.
Dealing with query #1
- Find position of winner at time t.
i.e. find out value of lower convex hull at time t.
We can use binary search to find the line which is the part of lower convex hull for a particular time.
After knowing the line, we can find the position of winner at that time t easily.
Dealing with query #2
- Change the speed of i-th racer from v to v’ at time T.
As discussed above, the old line corresponding to racer (x_i, v_i) has to be replaced with new line (x_i', v_i').
We are given in the problem statement that speed of a racer will never decrease.
So, we don’t need to delete the older line for an update, because it is not going to provide us position of winner of race anyways.
Hence we only need to support addition of line operation in a convex hull.
We can add a line in a lower convex hull using binary search too.
This operation is very well explained in the following article.
O((n + Q) log n)