题目描述
blablabla
样例
#include <iostream>
#include <vector>
using namespace std;
void changeValue(vector<vector<int>>& mat, int x1, int y1, int x2, int y2, int v) {
// 在坐标(注意这次坐标从1开始)[x1, x2]和[y1, y2]之间加上value
mat[x1][y1] += v;
mat[x2 + 1][y1] -= v;
mat[x1][y2 + 1] -= v;
mat[x2 + 1][y2 + 1] += v;
}
int main() {
int n = 0, m = 0, q = 0;
cin >> n >> m >> q;
vector<vector<int>> mat (n + 2, vector<int> (m + 2, 0));
for (int i = 1; i < n + 1; i ++) {
for (int j = 1; j < m + 1; j ++) {
int num = 0;
scanf("%d", &num);
// 直接将mat视为差分矩阵 假设初始矩阵为全0
// 权当读入arr时 我们直接改变差分矩阵即可
changeValue(mat, i, j, i, j, num);
}
}
while (q --) {
int x1 = 0, y1 = 0, x2 = 0, y2 = 0, c = 0;
cin >> x1 >> y1 >> x2 >> y2 >> c;
changeValue(mat, x1, y1, x2, y2, c);
}
// 再求前缀和 即得到操作后的 原数组
for (int i = 1; i < n + 1; i ++) {
for (int j = 1; j < m + 1; j ++) {
mat[i][j] += (mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1]);
cout << mat[i][j] << " ";
}
cout << "\n";
}
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla