二维差分

原理

紫色部分为所求区域，黄色区域为当前覆盖的区域。

$d[x1][y1] += w$ 表示将 $[x1, y1]$ 右下部分全部加上增量 $w$。

$d[x1][y2 + 1] -= w$ 用于抵消对 $y2$ 右边元素的影响，即图三蓝色区域。

$d[x2 + 1][y1] -= w$ 用于抵消对 $x2$ 下边元素的影响，即图四蓝色区域。

$d[x2 + 1][y2 + 1] += w$ 由于绿色区域被抵消了两次，因此需要加回增量 $w$。

Code

#include <bits/stdc++.h>
using namespace std;
int a[1005][1005], d[1005][1005];
int main() {
  int n, m, q, x1, y1, x2, y2, w;
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) cin >> a[i][j];
  while (q--) {
    cin >> x1 >> y1 >> x2 >> y2 >> w;
    d[x1][y1] += w;
    d[x1][y2 + 1] -= w;
    d[x2 + 1][y1] -= w;
    d[x2 + 1][y2 + 1] += w;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      d[i][j] -= d[i - 1][j - 1] - d[i - 1][j] - d[i][j - 1];
      a[i][j] += d[i][j];
      printf("%d ", a[i][j]);
    }
    printf("\n");
  }
  return 0;
}