An Interesting Problem

Правка en1, от EternalFire, 2018-11-02 07:06:01

Recently I have encountered an interesting problem:

Given a grid of N x M (1 <= N, M <= 1500) consist of integers. Define F(i, j) is the maximum value can be obtained by moving from (1, 1) to (i, j) using only moving right and moving down operation, i.e from (i, j) you can only move to (i + 1, j) and (i, j + 1). Your task is calculate sum of F(i, j) over 1 <= i <= N and 1 <= j <= M.

Now you have Q queries, each query denote by character c and two integers x and y. c is either '-' or '+'. If c is '-', then a[x][y]--, otherwise a[x][y]++. After each query you have to print on a line the sum of F(i, j) over 1 <= i <= N and 1 <= j <= M.

I couldn't optimize my O(n^3) algorithm. Could anyone have an idea to solve this problem?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский EternalFire 2018-11-02 10:30:24 2 Tiny change: 'of number in that pat' -> 'of number on that pat'
en3 Английский EternalFire 2018-11-02 10:22:23 58
en2 Английский EternalFire 2018-11-02 07:07:04 33
en1 Английский EternalFire 2018-11-02 07:06:01 762 Initial revision (published)