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.