← 返回题目列表

AtCoder · awc0070_d

D. 开关灯

中文机器翻译题面 查看原题

分数: 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