题目描述
难度分:2100
输入T(≤103)表示T组数据。所有数据的n之和≤2000。
每组数据输入n(1≤n≤2000)、q(1≤q≤106)和n行n列的矩阵a(1≤a[i][j]≤106)。
然后输入q个询问,每个询问输入四个数r1、c1、r2、c2,表示子矩阵左上角的行列编号、右下角的行列编号。编号从1开始。
把子矩形展开成一维数组A,也就是子矩阵的第一行 + 第二行 + 第三行 + … 拼起来。A的下标从1开始。输出1×A[1]+2×A[2]+3×A[3]+…+k×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
算法
构造+前缀和
这个题本质是个构造题,要想求得子矩阵(x1,y1,x2,x2)的累加和是比较容易的,利用二维前缀和可以O(1)求出来,令s为a的二维前缀和矩阵。但是元素前面乘了系数强度就上来了,我们需要构造一种累加和,让它减去一个定值可以得到目标和。
可以对第i行的元素都乘以i,第j列的元素乘以j,分别对这两种情况求和得到前缀和矩阵sx和sy。对第一种情况乘以矩阵的宽度y2−y1+1,然后把两种情况的子矩阵和加起来构造子矩阵(x1,y1,x2,x2)的元素系数
(x1×(y2−y1+1)+y1x1×(y2−y1+1)+y1+1…x1×(y2−y1+1)+y2(x1+1)×(y2−y1+1)+y1(x1+1)×(y2−y1+1)+y1+1…(x1+1)×(y2−y1+1)+y2…x2×(y2−y1+1)+y1x2×(y2−y1+1)+y1+1…x2×(y2−y1+1)+y2)
但其实我们想要的系数是
(12…y2−y1+1y2−y1+1+1y2−y1+1+2…y2−y1+1+y2−y1+1…(x2−x1)×(y2−y1+1)+y1(x2−x1)×(y2−y1+1)+y1+1…(x2−x1+1)×(y2−y1+1))
这两个矩阵做差,每个位置的元素就变成一样的了,均为(y2−y1+1)+y1−1。所以答案就应该是(y2−y1+1)×sumx+sumy−sum×(x1×(y2−y1+1)+y1−1)。其中sum是原始矩阵的二维前缀和,sumx是每行元素都乘以了行号之后的二维前缀和,sumy是每列元素都乘以了列号之后的二维前缀和。
复杂度分析
时间复杂度
预处理出二维前缀和的时间复杂度为O(n2)。计算每个询问的时间复杂度为O(1),要处理O(q)个询问。所以整个算法的时间复杂度为O(n2+q)。
空间复杂度
三个前缀和数组s、sx和sy就是空间消耗的瓶颈。因此,额外空间复杂度为O(n2)。
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;
}