During one of my problem solving sessions, I thought about this problem somewhat related to what I was solving:

Say you have a set of numbers a_1, a_2, ..., a_n and some values x_1, x_2, ..., x_n.

On this set, you can make the following operation:

a_1, a_2, ..., a_n ------> a_1 + x_1, a_2 + x_2, ..., a_n + x_n

(in other words, you add to each number its corresponding x value).

You have to repeat this operation many times and after each time answer what is the minimum element in the set. By many I mean (for example) that the number of elements and the number of queries have the same order.

If all x values are equal, it's easy to solve with something like segment tree. However, the way the problem is, I have tried different approaches (including some algebraic ones) but I can't seem to come up with a solution that is better than quadratic. It seems like it should be a simple problem, is there a simple solution I am not seeing?

UPDATE: reading random (completely unrelated) posts on codeforces, I have by chance found something called "Convex hull trick" which can be used to determine the minimum element from a set of linear functions evaluated at a certain point. It seems like it could be applied in this situation, since the value of a_i after k steps can be expressed a linear function in k: f_i(k) = a_i + k * x_i. This method would provide a linearithmic solution. I will check it out tomorrow.