分数: 466 分
问题陈述
高桥正在网格画布上玩绘画游戏 H 行和 W 列。牢房位于 i从顶部算起的第行和 j从左边算起的第列称为单元格 (i, j).
细胞 (i, j) 有一个分数 A_{i,j} 分配给它。最初,没有绘制任何单元格。
高桥将把颜料滴到画布上 Q 次。
在 t-th 油漆滴,画布上与单元格曼哈顿距离的所有单元格 (R_t, C_t) 最多是 D_t 已涂漆。
换句话说,在所有单元格中 (i, j) 满意 1 \leq i \leq H 和 1 \leq j \leq W,所有单元格满足
|i - R_t| + |j - C_t| \leq D_t
已涂漆。
当尚未绘制的单元格被新绘制时,高桥获得该单元格的分数。当油漆到达已涂漆的单元格时,不会获得任何分数。
对于每个油漆滴,找到高桥从该油漆滴中新获得的总分。
约束
- 1 \leq H \leq 2 \times 10^5
- 1 \leq W \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- H \times W \leq 4 \times 10^6
- H \times Q \leq 4 \times 10^6
- H + Q \leq 2 \times 10^5
- 0 \leq A_{i,j} \leq 10^9
- 1 \leq R_t \leq H
- 1 \leq C_t \leq W
- 0 \leq D_t \leq H + W
- 所有输入值均为整数
输入
H W
A_{1,1} A_{1,2} \cdots A_{1,W}
A_{2,1} A_{2,2} \cdots A_{2,W}
\vdots
A_{H,1} A_{H,2} \cdots A_{H,W}
Q
R_1 C_1 D_1
R_2 C_2 D_2
\vdots
R_Q C_Q D_Q
- 第一行包含行数 H 和列数 画布的 W ,以空格分隔。
- 在下面 H 行, i- 第行包含分数 A_{i,1}, A_{i,2}, \ldots, A_{i,W} 以空格分隔。
- 下一行包含油漆滴数 Q.
- 在下面 Q 行, t第行包含中心行 R_t,列 C_t,并到达距离 D_t 的 t第一个油漆滴,以空格分隔。
输出
输出 Q 行。
的 t- 第行应包含高桥新获得的总分 t-th 油漆滴。
样本输入 1
3 4 1 2 3 4 5 6 7 8 9 10 11 12 4 2 2 1 1 4 0 3 1 2 2 3 7
示例输出 1
30 4 21 23
示例输入 2
2 5 0 5 0 7 1 3 0 4 0 2 5 1 1 0 1 3 1 2 5 3 2 2 0 1 5 0
示例输出 2
0 16 3 0 0
示例输入 3
5 7 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 3 4 2 1 1 3 5 7 1 2 6 4 4 2 0 5 1 5 1 7 0 3 3 10
示例输出 3
52 30 13 46 6 18 0 0
示例输入 4
8 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 12 4 5 3 1 10 2 8 1 4 3 7 0 6 6 5 2 2 1 7 9 3 1 1 18 8 10 0 5 3 2 4 10 6 8 5 8
示例输出 4
875 96 885 0 1121 60 80 123 0 0 0 0
示例输入 5
1 1 1000000000 4 1 1 0 1 1 1 1 1 2 1 1 0
示例输出 5
1000000000 0 0 0