由于题目要求让子矩阵中的每一个值都加上一个数,因此很自然能够想到用差分来做。但难的是如何构建差分数组
差分实际上是前缀和的逆运算,因此输入的数组A为原数组,同时也为其差分数组的前缀和。故,数组B可以设为数组A的差分数组,那么如何得到B的值呢?我们可以类比一维差分的情况。
一维差分数组中,如果要对原数组的[l, r]区间同时加上c,那么需要在其差分数组的l位置加上c,在r + 1位置减上c,同理在二维差分数组中,对[x1, y1]位置加上c意味着在原数组的[x1, y1]的右下方位置全部加了数值c,因此还需要减去我们不需要的部分,即[x1, y2 + 1]位置与[x2 + 1, y1]位置减去c,这时会发现他们重叠了一个[x2 + 1, y2 + 1]的部分,因此需要对差分数组的[x2 + 1, y2 + 1]位置加上c。
现在我们知道了如何通过差分数组来对原数组进行添加数值了,因此我们可以这么想,假设现在数组A的值全部为0,我们就需要对数组A的每个位置插入一个数,这样是不是就用到了上述操作了呀?因此调用上面函数即可完成差分数组B的构建。
知道了差分数组B就好办了,我们还需要对数组A进行加减值的操作,继续调用函数即可完善差分数组B。
最后求差分数组B的前缀和就能够得到数组A了~
def insert(x1, y1, x2, y2, c):
global numsB
numsB[x1][y1] += c
numsB[x1][y2 + 1] -= c
numsB[x2 + 1][y1] -= c
numsB[x2 + 1][y2 + 1] += c
n, m, q = map(int, input().split())
numsA = [[0 for _ in range(m + 5)] for _ in range(n + 5)] #原数组
numsB = [[0 for _ in range(m + 5)] for _ in range(n + 5)] #差分数组
for i in range(1, n + 1):
row = list(map(int, input().split()))
for j in range(1, m + 1):
numsA[i][j] = row[j - 1]
for i in range(1, n + 1):
for j in range(1, m + 1):
insert(i, j, i, j, numsA[i][j]) #获得差分数组
for _ 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):
numsB[i][j] += numsB[i - 1][j] + numsB[i][j - 1] - numsB[i - 1][j - 1]
print(numsB[i][j], end = ' ')
print()