AcWing 798. 差分矩阵JAVA
原题链接
简单
作者:
理想二旬.
,
2021-05-03 17:52:30
,
所有人可见
,
阅读 283
JAVA 代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
//必须用BufferReader。
class Main{
static int N = 1010;
static int[][] a = new int[N][N];
static int[][] b = new int[N][N];
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[] str1 = reader.readLine().split(" ");
int n = Integer.parseInt(str1[0]);
int m = Integer.parseInt(str1[1]);
int q = Integer.parseInt(str1[2]);
//读入原数组
for(int i = 1; i <= n; i++){
String[] str2 = reader.readLine().split(" ");
for(int j = 1; j <= m; j++){
a[i][j] = Integer.parseInt(str2[j - 1]);
//初始化差分数组
insert(i, j, i, j, a[i][j]);
}
}
//加c
while(q-- > 0){
String[] str3 = reader.readLine().split(" ");
insert(Integer.parseInt(str3[0]), Integer.parseInt(str3[1]), Integer.parseInt(str3[2]), Integer.parseInt(str3[3]), Integer.parseInt(str3[4]));
}
//类似于求B的前缀和
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.write("\n");
}
writer.flush();
reader.close();
writer.close();
}
public static void insert(int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c;
b[x2 + 1][y1] -= c;
b[x1][y2 + 1] -= c;
b[x2 + 1][y2 + 1] += c;
}
}