D - Switching the Lights Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君はイベント会場に N 行 M 列のグリッド状に照明を設置しました。各照明には初期の明るさが設定されており、i 行 j 列目の照明の初期の明るさは B_{i,j} です。

高橋君はイベントの演出として、照明の明るさを調整することにしました。各照明にはスイッチが付いており、スイッチを 1 回押すごとに、その照明の状態が「通常モード」と「強調モード」の間で切り替わります。最初、すべての照明は通常モードです。

高橋君は Q 回のスイッチ操作を順に行います。k 回目 (1 \leq k \leq Q) の操作では、入力で指定された長方形領域、すなわち左上が (r1_k, c1_k) 、右下が (r2_k, c2_k) である領域内のすべての照明のスイッチを 1 回ずつ押します。ここで、照明 (i, j) がこの長方形領域内に含まれるとは、r1_k \leq i \leq r2_k かつ c1_k \leq j \leq c2_k を満たすことを意味します。

Q 回の操作がすべて終わった後、各照明の最終的な明るさは、その照明のモードによって以下のように決まります。

  • 強調モードの照明(スイッチが押された回数が奇数回):明るさは 2 \times B_{i,j}
  • 通常モードの照明(スイッチが押された回数が偶数回。0 回も偶数回に含む):明るさは B_{i,j}

すべての操作が終わった後の、会場全体の照明の明るさの合計を求めてください。

制約

  • 1 \leq N \leq 1500
  • 1 \leq M \leq 1500
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq B_{i,j} \leq 10^4
  • 1 \leq r1_k \leq r2_k \leq N
  • 1 \leq c1_k \leq c2_k \leq M
  • 入力はすべて整数である

入力

N M Q
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}
r1_1 c1_1 r2_1 c2_1
r1_2 c1_2 r2_2 c2_2
\vdots
r1_Q c1_Q r2_Q c2_Q
  • 1 行目には、グリッドの行数を表す整数 N 、列数を表す整数 M 、操作の回数を表す整数 Q が、スペース区切りで与えられる。
  • 続く N 行で、照明の初期の明るさが与えられる。
  • このうち i 行目 (1 \leq i \leq N) では、グリッドの i 行目の各列の明るさ B_{i,1}, B_{i,2}, \ldots, B_{i,M} がスペース区切りで与えられる。
  • 続く Q 行で、各操作の長方形領域が与えられる。
  • このうち k 行目 (1 \leq k \leq Q) では、k 回目の操作における長方形領域の左上の行番号 r1_k 、左上の列番号 c1_k 、右下の行番号 r2_k 、右下の列番号 c2_k がスペース区切りで与えられる。

出力

すべての操作が終わった後の、会場全体の照明の明るさの合計を整数として 1 行で出力せよ。


入力例 1

2 3 1
1 2 3
4 5 6
1 1 2 2

出力例 1

33

入力例 2

2 2 2
5 3
2 4
1 1 2 2
1 1 2 2

出力例 2

14

入力例 3

4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 3
2 2 4 4
1 1 4 4

出力例 3

175

入力例 4

5 6 5
10 20 30 40 50 60
15 25 35 45 55 65
12 22 32 42 52 62
18 28 38 48 58 68
11 21 31 41 51 61
1 1 3 4
2 3 5 6
1 1 5 6
3 2 4 5
1 5 2 6

出力例 4

1614

入力例 5

1 1 1
7
1 1 1 1

出力例 5

14

Score : 400 pts

Problem Statement

Takahashi has installed lights in an N-row by M-column grid at an event venue. Each light has an initial brightness setting, and the initial brightness of the light at row i, column j is B_{i,j}.

As part of the event's production, Takahashi decided to adjust the brightness of the lights. Each light has a switch, and each time the switch is pressed, the light toggles between "normal mode" and "enhanced mode." Initially, all lights are in normal mode.

Takahashi performs Q switch operations in order. In the k-th operation (1 \leq k \leq Q), he presses the switch once for every light within the rectangular region specified by the input, namely the region with top-left corner (r1_k, c1_k) and bottom-right corner (r2_k, c2_k). Here, light (i, j) is contained in this rectangular region if and only if r1_k \leq i \leq r2_k and c1_k \leq j \leq c2_k.

After all Q operations are completed, the final brightness of each light is determined by its mode as follows:

  • Enhanced mode lights (switch pressed an odd number of times): brightness is 2 \times B_{i,j}
  • Normal mode lights (switch pressed an even number of times; 0 counts as even): brightness is B_{i,j}

Find the total brightness of all lights in the venue after all operations are completed.

Constraints

  • 1 \leq N \leq 1500
  • 1 \leq M \leq 1500
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq B_{i,j} \leq 10^4
  • 1 \leq r1_k \leq r2_k \leq N
  • 1 \leq c1_k \leq c2_k \leq M
  • All input values are integers

Input

N M Q
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}
r1_1 c1_1 r2_1 c2_1
r1_2 c1_2 r2_2 c2_2
\vdots
r1_Q c1_Q r2_Q c2_Q
  • The first line contains three space-separated integers: N representing the number of rows in the grid, M representing the number of columns, and Q representing the number of operations.
  • The following N lines give the initial brightness of the lights.
  • The i-th of these lines (1 \leq i \leq N) contains the brightness values B_{i,1}, B_{i,2}, \ldots, B_{i,M} of each column in row i of the grid, separated by spaces.
  • The following Q lines give the rectangular region for each operation.
  • The k-th of these lines (1 \leq k \leq Q) contains four space-separated values: the top-left row number r1_k, the top-left column number c1_k, the bottom-right row number r2_k, and the bottom-right column number c2_k for the k-th operation.

Output

Output the total brightness of all lights in the venue after all operations are completed, as a single integer on one line.


Sample Input 1

2 3 1
1 2 3
4 5 6
1 1 2 2

Sample Output 1

33

Sample Input 2

2 2 2
5 3
2 4
1 1 2 2
1 1 2 2

Sample Output 2

14

Sample Input 3

4 4 3
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
1 1 2 3
2 2 4 4
1 1 4 4

Sample Output 3

175

Sample Input 4

5 6 5
10 20 30 40 50 60
15 25 35 45 55 65
12 22 32 42 52 62
18 28 38 48 58 68
11 21 31 41 51 61
1 1 3 4
2 3 5 6
1 1 5 6
3 2 4 5
1 5 2 6

Sample Output 4

1614

Sample Input 5

1 1 1
7
1 1 1 1

Sample Output 5

14