/
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