1916. 二维差分

模板题,不解释代码及一般步骤。注意开动态数组和long long,注意下标范围是 [0,n+1][0,m+1],所以要开大至少两位。

#include <bits/stdc++.h> using namespace std; using ll = long long; signed main() { ios::sync_with_stdio(false), cin.tie(0); ll n, m, t; cin >> n >> m >> t; vector<vector<ll>> A(n + 2, vector<ll>(m + 2, 0)); // [0,n+1],[0,m+1] for (ll a, b, c, d, v; t--;) { cin >> a >> b >> c >> d >> v; A[a][c] += v; A[b + 1][c] -= v; A[a][d + 1] -= v; A[b + 1][d + 1] += v; } for (ll i = 1; i <= n; ++i) { for (ll j = 1; j <= m; ++j) { A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1]; cout << A[i][j] << ' '; } cout << '\n'; } return 0; }