分数: 400 点
问题陈述
给你一个正整数 N,和一个整数 A_{x,y,z} 对于每个整数三元组 (x, y, z) 这样 1 \leq x, y, z \leq N.
你将得到 Q 查询格式如下,必须按顺序处理。
对于 i第一个查询 (1 \leq i \leq Q),给你一个整数元组 (Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i) 这样 1 \leq Lx_i \leq Rx_i \leq N, 1 \leq Ly_i \leq Ry_i \leq N,和 1 \leq Lz_i \leq Rz_i \leq N。查找:
\displaystyle{\sum_{x=Lx_i}^{Rx_i} \sum_{y=Ly_i}^{Ry_i} \sum_{z=Lz_i}^{Rz_i} A_{x,y,z}}.
约束
- 1 \leq N \leq 100
- 1 \leq Q \leq 2 \times 10^{5}
- 0 \leq A_{x,y,z} \leq 999 (1 \leq x, y, z \leq N)
- 1 \leq Lx_i \leq Rx_i \leq N (1 \leq i \leq Q)
- 1 \leq Ly_i \leq Ry_i \leq N (1 \leq i \leq Q)
- 1 \leq Lz_i \leq Rz_i \leq N (1 \leq i \leq Q)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N
A_{1,1,1} A_{1,1,2} \ldots A_{1,1,N}
A_{1,2,1} A_{1,2,2} \ldots A_{1,2,N}
\vdots
A_{1,N,1} A_{1,N,2} \ldots A_{1,N,N}
A_{2,1,1} A_{2,1,2} \ldots A_{2,1,N}
A_{2,2,1} A_{2,2,2} \ldots A_{2,2,N}
\vdots
A_{2,N,1} A_{2,N,2} \ldots A_{2,N,N}
\vdots
A_{N,1,1} A_{N,1,2} \ldots A_{N,1,N}
A_{N,2,1} A_{N,2,2} \ldots A_{N,2,N}
\vdots
A_{N,N,1} A_{N,N,2} \ldots A_{N,N,N}
Q
Lx_1 Rx_1 Ly_1 Ry_1 Lz_1 Rz_1
Lx_2 Rx_2 Ly_2 Ry_2 Lz_2 Rz_2
\vdots
Lx_Q Rx_Q Ly_Q Ry_Q Lz_Q Rz_Q
输出
打印 Q 行。 的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
2 1 2 3 4 5 6 7 8 2 1 2 2 2 1 1 2 2 1 2 1 2
示例输出 1
10 26
对于第一个查询,查找的值为 A_{1,2,1} + A_{2,2,1} = 3 + 7 = 10。因此,打印 10.
对于第二个查询,查找的值为 A_{2,1,1} + A_{2,1,2} + A_{2,2,1} + A_{2,2,2} = 5 + 6 + 7 + 8 = 26。因此,打印 26.
示例输入 2
3 733 857 714 956 208 257 123 719 648 840 881 245 245 112 746 306 942 694 58 870 849 13 208 789 687 906 783 8 3 3 3 3 1 1 1 3 2 3 3 3 2 2 2 3 1 1 1 3 1 1 1 1 2 3 2 3 2 3 1 2 1 1 1 2 3 3 2 2 1 3 1 2 2 3 2 3
示例输出 2
687 3917 551 1631 5180 3311 1010 4326