← 返回题目列表

Codeforces · 2044/H

H. 硬恶魔问题

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

Swing要开煎饼厂了!一个好的煎饼工厂必须擅长把东西压平,所以 Swing 打算在 2D 矩阵上测试他的新设备。

Swing 被赋予一个包含正整数的 $$$n \times n$$$ 矩阵 $$$M$$$。他有 $$$q$$$ 问题要问你。

对于每个查询,他都会给你四个整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$、$$$y_2$$$ 并要求你将 $$$(x_1, y_1)$$$ 和 $$$(x_2, y_2)$$$ 边界的子矩阵展平为一个数组$$$A$$$。形式上,$$$A = [M_{(x1,y1)}, M_{(x1,y1+1)}, \ldots, M_{(x1,y2)}, M_{(x1+1,y1)}, M_{(x1+1,y1+1)}, \ldots, M_{(x2,y2)}]$$$。

下图描绘了由红色虚线界定的子矩阵的展平。橙色箭头表示子矩阵的元素附加到$$$A$$$后面的方向,$$$A$$$显示在图像的底部。

然后,他询问你 $$$\sum_{i=1}^{|A|} A_i \cdot i$$$ 的值($$$A_i \cdot i$$$ 与所有 $$$i$$$ 的总和)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n \leq 2000, 1 \leq q \leq 10^6$$$) — $$$M$$$ 的长度和查询数量。

以下 $$$n$$$ 行每行包含 $$$n$$$ 个整数,其中第 $$$i$$$ 包含 $$$M_{(i,1)}, M_{(i,2)}, \ldots, M_{(i,n)}$$$ ($$$1 \leq M_{(i, j)} \leq 10^6$$$)。

以下 $$$q$$$ 行包含四个整数 $$$x_1$$$、$$$y_1$$$、$$$x_2$$$ 和 $$$y_2$$$ ($$$1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n$$$) —查询。

保证所有测试用例的$$$n$$$总和不超过$$$2000$$$,所有测试用例的$$$q$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,在新行中输出 $$$q$$$ 查询的结果。

示例

输入 #1

2
4 3
1 5 2 4
4 9 5 3
4 5 2 3
1 5 5 2
1 1 4 4
2 2 3 3
1 2 4 3
3 3
1 2 3
4 5 6
7 8 9
1 1 1 3
1 3 3 3
2 2 2 2

输出 #1

500 42 168 
14 42 5

注意

在第一个测试用例的第二个查询中,$$$A = [9, 5, 5, 2]$$$。因此,总和为 $$$1 \cdot 9 + 2 \cdot 5 + 3 \cdot 5 + 4 \cdot 2 = 42$$$。