思路
1、创建一个(n+10)行(m+10)列的差分数组diff,并将其初始化为全零。
2、遍历输入的矩阵sequ,将sequ中的每个元素插入到差分数组diff中。对于sequ中的每个元素sequ[i][j] ,将其插入到差分数组diff中的对应位置(i,j)。具体操作是,将diff[x1][y1]增加c,将diff[x2+ 1][y1]减去c,将diff[x1][y2+1]减去c,将diff[x2+1][y2+1]增加c。
3、接下来,对于每个操作,将操作区域对应的差分数组元素进行更新。具体操作是,将diff[x1][y1] 增加c,将diff[x2+1][y1]减去c,将diff[x1][y2+1]减去c,将diff[x2+1][y2+1]增加c。
4、最后,遍历差分数组diff,对于每个元素diff[i][j],将其更新为diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] + diff[i][j]。
5、输出更新后的差分数组diff。
时间复杂度
O(n*m + q)
def insert(diff, x1, y1, x2, y2, c):
diff[x1][y1] += c
diff[x2+1][y2+1] += c
diff[x1][y2+1] -= c
diff[x2+1][y1] -= c
if __name__ =="__main__":
n, m, q = map(int, input().split())
sequ=[[0]*(m + 10) for i in range(n + 10)]
diff=[[0]*(m + 10) for i in range(n + 10)]
for i in range(n):
sequ[i+1][1:] = list(map(int, input().split()))
for i in range(1, n+1):
for j in range(1, m+1):
insert(diff, i, j, i, j, sequ[i][j])
for i in range(q):
x1, y1, x2, y2, c = map(int, input().split())
insert(diff, x1, y1, x2, y2, c)
for i in range(1, n+1):
for j in range(1, m+1):
diff[i][j] = diff[i][j-1] + diff[i-1][j] - diff[i-1][j-1] + diff[i][j]
print(diff[i][j], end=" ")
print()
能力有限,如果python有更好的解决方案,望告知