WHCSRL 技术网

C++题解 差分矩阵

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\ 1n,m10001q1000001x1x2n1y1y2m1000c100010001000

输入样例:

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
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

输出样例:

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

思想

差分

差分是前缀和的逆运算,通过差分,我们可以实现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;
  • 1
  • 2
  • 3
  • 4

此处借用[@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,才能使其恢复。

1

矩阵和计算

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,j1]+S[i1,j]S[i1,j1]+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 << "
";
    }

    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
推荐阅读