An Interesting Problem

Revision en1, by 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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English EternalFire 2018-11-02 10:30:24 2 Tiny change: 'of number in that pat' -> 'of number on that pat'
en3 English EternalFire 2018-11-02 10:22:23 58
en2 English EternalFire 2018-11-02 07:07:04 33
en1 English EternalFire 2018-11-02 07:06:01 762 Initial revision (published)