主体思路
先算出差分矩阵,再算其前缀和矩阵
注意细节
别忘了把差分矩阵转回原矩阵
标准代码
package main
import (
"bufio"
"os"
"fmt"
)
var (
n, m, q, x1, y1, x2, y2, c int
nums, b [][]int
in = bufio.NewReader(os.Stdin)
out = bufio.NewWriter(os.Stdout)
)
func diff(x1, y1, x2, y2, c int) { // 核心:初始化 或者 计算
b[x1][y1] += c
b[x2 + 1][y1] -= c
b[x1][y2 + 1] -= c
b[x2 + 1][y2 + 1] += c
}
func main() {
fmt.Fscan(in, &n, &m, &q)
nums, b = make([][]int, n + 1), make([][]int, n + 2)
for i := range nums { nums[i] = make([]int, m + 1) }
for i := range b { b[i] = make([]int, m + 2) }
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
fmt.Fscan(in, &nums[i][j])
diff(i, j, i, j, nums[i][j]) // 初始化差分矩阵
}
}
for ; q > 0; q-- {
fmt.Fscan(in, &x1, &y1, &x2, &y2, &c)
diff(x1, y1, x2, y2, c) // 用差分矩阵进行计算
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] // 用二维前缀和公式将差分矩阵还原为初始矩阵
}
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
fmt.Fprint(out, b[i][j], " ")
}
fmt.Fprint(out, "\n")
}
out.Flush()
}