Singularity Cup P4 - Staircase Sum

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 3.5s
Memory limit: 256M

Problem type

Given an N \times M grid of integers G, you will be asked to perform Q operations on it. Each operation is one of the following:

  1. Update the integer at some (r, c) to v.
  2. Query the "staircase sum" at some (r, c) with height h.

A "staircase sum" is defined as follows: starting at (r, c), get the sum of every column from (r, c) to (r, c+h-1) with the first column going from (r, c) to (r-h+1, c) and then descending by 1 unit of height for each subsequent column.

More formally, the "staircase sum" at some (r, c, h) is equivalent to \sum_{x=1}^{h} \sum_{y=1}^{h-x+1} G_{(r-y+1)(c+x-1)}.

You will be asked to answer Q of the operations described above. For each operation of type 2, output the desired result.


1 \le N, M \le 2000

1 \le Q \le 10^6

-10^6 \le G_{ij} \le 10^6

1 \le r \le N

1 \le c \le M

Operation 1

-10^6 \le v \le 10^6

Operation 2

h \ge 1

r-h+1 \ge 1

c+h-1 \le M

Subtask 1 [30%]

Q \le 10^5

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input contains integers N, M, and Q.

The next N lines of input each contain M space-separated integers representing G.

The next Q lines of input each contain 4 space-separated integers in the format 1 r c v or 2 r c h.

Output Specification

For each type 2 operation, output the "staircase sum" of the grid after applying any previous type 1 operations.

Sample Input

4 4 3
6 1 0 2
1 1 1 1
2 2 2 2
3 0 3 -3
1 4 2 7
2 1 1 1
2 4 2 3

Sample Output


Explanation for Sample

The result of the final operation is obtained by adding the numbers highlighted below:



There are no comments at the moment.