分数: 400 分
问题陈述
高桥在一个房间里安装了灯 N-行按 M- 活动场地的柱状网格。每个灯都有一个初始亮度设置,行上灯的初始亮度 i,列 j is B_{i,j}.
作为活动制作的一部分,高桥决定调整灯光的亮度。每个灯都有一个开关,每次按下开关,灯就会在“正常模式”和“增强模式”之间切换。最初,所有灯都处于正常模式。
高桥表演 Q 按顺序切换操作。在 k第次操作 (1 \leq k \leq Q),他在输入指定的矩形区域(即左上角的区域)内每点亮一个灯就按一次开关 (r1_k, c1_k) 和右下角 (r2_k, c2_k)。在这里,光 (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
- 第一行包含三个空格分隔的整数: N 表示网格中的行数, M 代表列数,以及 Q 代表操作次数。
- 以下 N 线给出了灯光的初始亮度。
- 的 i- 第这些行 (1 \leq i \leq N) 包含亮度值 行中每列的 B_{i,1}, B_{i,2}, \ldots, B_{i,M} 网格的 i ,用空格分隔。
- 以下 Q 行给出每个操作的矩形区域。
- 的 k- 第这些行 (1 \leq k \leq Q) 包含四个空格分隔的值:左上角的行号 r1_k,左上角的列号 c1_k,右下行号 r2_k,以及右下角的列号 c2_k 为 k-第次操作。
输出
所有操作完成后,将场内所有灯光的总亮度输出为一行上的单个整数。
示例输入 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