A18846. 基础子矩阵求和
填空题
较难
知识点
题目描述
基础子矩阵求和
题目描述
给定一个n行m列的整数矩阵，再给出q次询问，每次询问给出四个整数x1,y1,x2,y2，代表子矩阵的左上角和右下角坐标（坐标均为1下标），请输出每次询问的子矩阵元素和。
输入格式
第一行三个整数n,m,q（1≤n,m≤100，1≤q≤1000）
接下来n行，每行m个整数，代表矩阵元素
接下来q行，每行四个整数x1,y1,x2,y2
输出格式
对于每个询问，输出一行一个整数，表示对应子矩阵的和
样例输入
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3样例输出
12
28参考答案
#include <iostream>
using namespace std;
const int N = 105;
int a[N][N], sum[N][N];
int main()
{
int n, m, q;
cin >> n >> m >> q;
// 读入矩阵
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
// 预处理二维前缀和
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];
// 处理查询
while(q--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int res = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
cout << res << endl;
}
return 0;
}
上一题
下一题