798. 差分矩阵
摘要
Title: 798. 差分矩阵
Tag: 二维差分
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
798. 差分矩阵
-
题意
输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。 -
思路
其实这些数，都是在处理二维前缀和的数+1得到的
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37'''
Author: NEFU AB-IN
Date: 2022-02-22 17:09:24
FilePath: \ACM\Acwing\798.py
LastEditTime: 2022-02-22 17:09:25
'''
N = int(1e3 + 10)
a = [[0] * N for _ in range(N)]
b = [[0] * N for _ in range(N)]
def insert(x1, y1, x2, y2, c):
b[x1][y1] += c
b[x1][y2 + 1] -= c
b[x2 + 1][y1] -= c
b[x2 + 1][y2 + 1] += c
n, m, q = map(int, input().split())
for i in range(1, n + 1):
a[i][1:] = list(map(int, input().split()))
for i in range(1, n + 1):
for j in range(1, m + 1):
insert(i, j, i, j, a[i][j]) #差分数组初始化
for i in range(q):
x1, y1, x2, y2, c = map(int, input().split())
insert(x1, y1, x2, y2, c)
for i in range(1, n + 1):
for j in range(1, m + 1):
a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j] #对b数组求前缀和，正好可以用a数组替代
print(a[i][j], end=" ")
print()
