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\ 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
- 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,才能使其恢复。
矩阵和计算
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 << "
";
}
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