Hi guys. Today I was solving a problem together with minimario and we came across a well known-looking subproblem we couldn't solve.
There are two sequences of length N, A[] and B[] with N, A[i], B[i] <= 10^5.
Our goal is to answer queries: a, b, x, y which mean : find the i in range <a, b> with the biggest value of A[i] * x + B[i] * y. 1 <= a <= b <= n, -10^5 <= x, y <= 10^5.
Is it possible to do it offline?
Is it possible with operation erase as well? (erase can be seen as setting A[i] = -inf and B[i] = -inf).
Thanks for any suggestions.