题目描述

难度分:$2100$

输入$T(\leq 10^3)$表示$T$组数据。所有数据的$n$之和$\leq 2000$。

每组数据输入$n(1 \leq n \leq 2000)$、$q(1 \leq q \leq 10^6)$和$n$行$n$列的矩阵$a(1 \leq a[i][j] \leq 10^6)$。

然后输入$q$个询问，每个询问输入四个数$r_1$、$c_1$、$r_2$、$c_2$，表示子矩阵左上角的行列编号、右下角的行列编号。编号从$1$开始。

把子矩形展开成一维数组$A$，也就是子矩阵的第一行 + 第二行 + 第三行 + … 拼起来。$A$的下标从$1$开始。输出$1 \times A[1] + 2 \times A[2] + 3 \times A[3] + … + k \times A[k]$，其中$k$是数组$A$的长度。

注：由于数据量大，使用快读可以显著减少运行时间。

输入样例

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

输出样例

500 42 168 
14 42 5 

算法

构造+前缀和

这个题本质是个构造题，要想求得子矩阵$(x_1,y_1,x_2,x_2)$的累加和是比较容易的，利用二维前缀和可以$O(1)$求出来，令$s$为$a$的二维前缀和矩阵。但是元素前面乘了系数强度就上来了，我们需要构造一种累加和，让它减去一个定值可以得到目标和。

可以对第$i$行的元素都乘以$i$，第$j$列的元素乘以$j$，分别对这两种情况求和得到前缀和矩阵$sx$和$sy$。对第一种情况乘以矩阵的宽度$y_2-y_1+1$，然后把两种情况的子矩阵和加起来构造子矩阵$(x_1,y_1,x_2,x_2)$的元素系数

$\begin{pmatrix} x_1 \times (y_2-y_1+1)+y_1 & x_1 \times (y_2-y_1+1)+y_1+1 & \dots & x_1 \times (y_2-y_1+1)+y_2 \\ (x_1+1) \times (y_2-y_1+1)+y_1 & (x_1+1) \times (y_2-y_1+1)+y_1+1 & \dots & (x_1+1) \times (y_2-y_1+1)+y_2 \\ \dots \\ x_2 \times (y_2-y_1+1)+y_1 & x_2 \times (y_2-y_1+1)+y_1+1 & \dots & x_2 \times (y_2-y_1+1)+y_2 \end{pmatrix}$

但其实我们想要的系数是

$\begin{pmatrix} 1 & 2 & \dots & y_2-y_1+1 \\ y_2-y_1+1+1 & y_2-y_1+1+2 & \dots & y_2-y_1+1+y_2-y_1+1 \\ \dots \\ (x_2-x_1) \times (y_2-y_1+1)+y_1 & (x_2-x_1) \times (y_2-y_1+1)+y_1+1 & \dots & (x_2-x_1+1) \times (y_2-y_1+1) \end{pmatrix}$

这两个矩阵做差，每个位置的元素就变成一样的了，均为$(y_2-y_1+1)+y_1-1$。所以答案就应该是$(y_2-y_1+1) \times sumx + sumy-sum \times (x_1 \times (y_2-y_1+1)+y_1-1)$。其中$sum$是原始矩阵的二维前缀和，$sumx$是每行元素都乘以了行号之后的二维前缀和，$sumy$是每列元素都乘以了列号之后的二维前缀和。

复杂度分析

时间复杂度

预处理出二维前缀和的时间复杂度为$O(n^2)$。计算每个询问的时间复杂度为$O(1)$，要处理$O(q)$个询问。所以整个算法的时间复杂度为$O(n^2+q)$。

空间复杂度

三个前缀和数组$s$、$sx$和$sy$就是空间消耗的瓶颈。因此，额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 2010;
int t, n, q;
LL a, s[N][N], sx[N][N], sy[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin.tie(0);
    cin >> t;
    while(t--) {
        cin >> n >> q;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                cin >> a;
                s[i][j] = a + s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
                sx[i][j] = i*a + sx[i - 1][j] + sx[i][j - 1] - sx[i - 1][j - 1];
                sy[i][j] = j*a + sy[i - 1][j] + sy[i][j - 1] - sy[i - 1][j - 1];
            }
        }
        while(q--) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            int len = y2 - y1 + 1;
            LL sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            LL sum_x = sx[x2][y2] - sx[x1 - 1][y2] - sx[x2][y1 - 1] + sx[x1 - 1][y1 - 1];
            LL sum_y = sy[x2][y2] - sy[x1 - 1][y2] - sy[x2][y1 - 1] + sy[x1 - 1][y1 - 1];
            cout << len*sum_x + sum_y - sum*(x1 * len + y1 - 1) << ' ';
        }
        cout << '\n';
    }
    return 0;
}