题目描述
blablabla
样例
import java.io.*;
class Main {
// 我们需要频繁的计算某个矩阵某一部分变化,这样复杂度会超。
// 所以我们可以用差分来辅助 给定一个范围从(x1, y1) -> (x2, y2) 变化c . 根据差分只要(x1, y1)的点增大c,
//之后的我们计算prefixsum的时候 从(x1, y1) -> (n, m) 所有的prefixsum都增大了c
//因为(x1, y1)增大了c 这个增加的c 参加了计算其他的prefixsum中 而我们知道这个prefixsum就可以是原数组真正的值
// 也就是这些其他位置也都增加了c 就是起到了区域增加的效果 但有些没增加的我们除掉就行了 在下面有介绍
static int[][] a, b;
// b是差分矩阵 然后a(i, j) 是b(i, j) 的prefixsum a(i, j) = a(i - 1, j) + a(i, j - 1) - a(i - 1, j - 1) + b(i, j)
//参考prefixsum 假设还有个矩阵 c(i, j) 是a(i, j) 的prefixsum c(i, j) = c(i - 1, j) + c(i, j - 1) - c(i - 1, j - 1) + a(i, j)
// 也就是代表Prefixsum的矩阵都是利用prefixsum[i][j] = prefixsum[i - 1][j] + prefixsum[i][j - 1] - prefixsum[i - 1][j - 1] + xx
// prefixsum[i][j] 是代表整个从(1, 1) -> (i, j)的sum 可以理解为一个状态
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] strs = reader.readLine().split(" ");
int n = Integer.parseInt(strs[0]), m = Integer.parseInt(strs[1]), q = Integer.parseInt(strs[2]);
a = new int[n + 1][m + 1];
b = new int[n + 2][m + 2]; // 后面的[x2 + 1][y2 + 1] 可能越界 所以
//用BufferedReader一次 就是得到整行的数据 我们当然也可以先用a[i][j] 来记录结果再insert但是这样也可以
for (int i = 1; i <= n; i++) {
String[] strs1 = reader.readLine().split(" "); // x就是i 但对于y 因为strs1 index是[0, m - 1] j需要+ 1 才是实际y
for (int j = 0; j < m; j++) {
int c = Integer.parseInt(strs1[j]);
insert(i, j + 1, i, j + 1, c);
}
}
while (q-- > 0) {
String[] strs2 = reader.readLine().split(" ");
int x1 = Integer.parseInt(strs2[0]), y1 = Integer.parseInt(strs2[1]);
int x2 = Integer.parseInt(strs2[2]), y2 = Integer.parseInt(strs2[3]);
int c = Integer.parseInt(strs2[4]);
insert(x1, y1, x2, y2, c);
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];
writer.write(a[i][j] + " ");
}
writer.newLine();
}
reader.close();
writer.flush();
writer.close();
}
public static void insert(int x1, int y1, int x2, int y2, int c) {
// x x x x x x x
// x x d c c a a (x1, y1) -> (x1, y2 + 1)
// x x c c d a a (x2, y2) -> (x2 + 1, y1)
// x x a a a a a (x2 + 1, y2 + 1)
// 从left-top (x1, y1) -> right-bottom (x2, y2) 可以看出如果把 这两个点变成d 其他变化的部分变成c
// 然后我们知道计算a 也就是b的prefixsum的时候 这一段变化 会影响所有d c a部分的prefixsum 但a部分我们不是prefixsum
// 所以我们在计算
// 然后(x2 + 1, y)
//
b[x1][y1] += c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y1] -= c;
b[x2 + 1][y2 + 1] += c;
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla