A Difference Array Problem

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 2.0s
Java 2.5s
Python 2.5s
Memory limit: 512M

Author:
Problem type

You are given a \(2\)-dimensional grid of size \(N \times N\), and \(Q\) queries:

\(1\ x_1\ y_1\ x_2\ y_2\ v\). This means adding \(v\) to all elements in the subgrid starting at \((x_1, y_1)\) and ending at \((x_2, y_2)\). \( (-1\ 000 \le v \le 1\ 000, 1 \le x_1 \le x_2 \le N, 1 \le y_1 \le y_2 \le N)\).

\(2\ x\ y\). This query asks for the value of the element at position \((x, y)\). \((1 \le x, y \le N)\).

All elements in the grid start off at a value of \(0\).

Input Specification

The first line will contain two integers \(N, Q\ (1 \le N \le 5\ 000, 1 \le Q \le 10^5)\).

The next \(Q\) lines will each contain a valid query as described above.

Output Specification

For each type \(2\) query, output the value of the element at position \((x, y)\) on its own line.

Subtasks

Subtask 1 [10%]

\(N \le 100, Q \le 100\)

Subtask 2 [30%]

\(x_1 = x_2 = x = 1, N \le 1\ 000\)

Subtask 3 [60%]

No further constraints.

Sample Input

4 6
1 1 1 3 3 2
2 3 3
1 2 3 4 4 1
1 3 3 3 3 100
2 4 4
2 2 3

Sample Output

2
1
3

Comments