A simple data structures problem.

Правка en1, от kpw29, 2017-07-31 00:51:02

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский kpw29 2017-07-31 00:51:02 613 Initial revision (published)