C++题解 差分矩阵

输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个操作，每个操作包含五个整数 x 1 , y 1 , x 2 , y 2 , c x_1,y_1,x_2,y_2,c x1​,y1​,x2​,y2​,c ，其中 ( x 1 , y 1 ) 和 ( x 2 , y 2 ) (x_1,y_1) 和 (x_2,y_2) (x1​,y1​)和(x2​,y2​) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c c c。

请你将进行完所有操作后的矩阵输出。

第一行包含整数 n , m , q n,m,q n,m,q。

接下来 n n n 行，每行包含 m m m个整数，表示整数矩阵。

接下来 q q q 行，每行包含 5 5 5 个整数 x 1 , y 1 , x 2 , y 2 , c x_1,y_1,x_2,y_2,c x1​,y1​,x2​,y2​,c，表示一个操作。

共 n n n 行，每行 m m m 个整数，表示所有操作进行完毕后的最终矩阵。

1 ≤ n , m ≤ 1000 1 ≤ q ≤ 100000 1 ≤ x 1 ≤ x 2 ≤ n 1 ≤ y 1 ≤ y 2 ≤ m − 1000 ≤ c ≤ 1000 − 1000 ≤ 矩 阵 内 元 素 的 值 ≤ 1000 1≤n,m≤1000\ 1≤q≤100000\ 1≤x_1≤x_2≤n\ 1≤y_1≤y_2≤m\ −1000≤c≤1000\ −1000≤矩阵内元素的值≤1000\ 1≤n,m≤10001≤q≤1000001≤x1​≤x2​≤n1≤y1​≤y2​≤m−1000≤c≤1000−1000≤矩阵内元素的值≤1000

3 4 3
1 2 2 1
3 2 2 1
1 1 1 1
1 1 2 2 1
1 3 2 3 2
3 1 3 4 1

2 3 4 1
4 3 4 1
2 2 2 2

差分是前缀和的逆运算，通过差分，我们可以实现O（1）的，对矩阵指定区间进行加减操作

首先给定一个原矩阵a：a[1][q], a[1][2], a[1][3],,,,,, a[n][n];

然后我们构造一个矩阵b ：b[1][1] ,b[1][2] , b[1][3],,,,,, b[n][n];

使得 a[i][i] = b[1][1] + b[1][2]+ b[1][3] +,,,,,, + b[i][i]

也就是说，a矩阵是b矩阵的前缀和矩阵，反过来我们把b矩阵叫做a矩阵的差分矩阵。换句话说，每一个a[i][i]都是b矩阵中从头开始的一段矩阵和。

我们假定原矩阵a全为0，给原矩阵a赋初始值的过程视为 对原矩阵a进行 单位为1的加减操作

我要对a矩阵的【l,r】进行加add操作，则我对差分矩阵b进行如下操作

	b[x1][y1] += add;
    b[x2 + 1][y1] -= add;
    b[x1][y2 + 1] -= add;
    b[x2 + 1][y2 + 1] += add;

此处借用[@z林深时见鹿]的图

b[x1][ y1 ] +=c; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。
b[x1,][y2+1]-=c ; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y1]- =c ; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。
b[x2+1][y2+1]+=c; 对应图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，再加上一次c，才能使其恢复。

S [ i , j ] S[i,j] S[i,j]即为图1红框中所有数的的和为：
S [ i , j ] = S [ i , j − 1 ] + S [ i − 1 , j ] − S [ i − 1 , j − 1 ] + a [ i , j ] S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j] S[i,j]=S[i,j−1]+S[i−1,j]−S[i−1,j−1]+a[i,j]

//
// Created by Owwkmidream on 2021/10/30.
//
#include "iostream"

using namespace std;

const int N = 1010;

int a[N][N], b[N][N];

void insert(int x1, int y1, int x2, int y2, int add)
{
    b[x1][y1] += add;
    b[x2 + 1][y1] -= add;
    b[x1][y2 + 1] -= add;
    b[x2 + 1][y2 + 1] += add;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n,m,q;
    cin >> n >> m >> q;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int tmp;
            cin >> tmp;
            insert(i ,j, i, j, tmp);
        }
    }

    int x1, x2, y1, y2, c;
    while (q -- ) {
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        insert(x1, y1, x2, y2, c);
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i][j];
            cout << a[i][j] << " ";
        }
        cout << "n";
    }

    return 0;
}