AcWing 798. 差分矩阵
2022/8/11 6:26:53
本文主要是介绍AcWing 798. 差分矩阵,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二维差分
我们已经知道了一维差分如何去做,那么如果扩展到二维呢?这里就要引入二维差分了。
定义
给定一个数组 \(a\),构造一个数组 \(b\),使得 \(a\) 数组是 \(b\) 数组的前缀和数组,那么称 \(b\) 数组是 \(a\) 数组的差分数组。
作用
在 \(O(1)\) 的复杂度内将原矩阵中的任意子矩阵的每个数加上 \(c\)(减法相同)。
具体实现 & 原理
如何构造差分数组?
我们先来考虑如何在 在 \(O(1)\) 的复杂度内将原矩阵中的任意子矩阵的每个数加上/减去 \(c\)。
将上述操作封装成函数形式:
void insert(int i, int j, int x, int y, int c) { b[i][j] += c; b[i][y + 1] -= c; b[x + 1][j] -= c;; b[x + 1][y + 1] += c; }
我们可以让 \(a\) 数组初始时为空,那么显然 \(b\) 数组也为空。
假设 \(a_{i, j}\) 这个格子里的数为 \(c\),怎么把它加上呢?
可以将左上角 \((i, j)\)、右下角 \((i, j)\) 的子矩形加上 \(c\)(其实就是把 \((i, j)\) 这个小方格加上 \(c\))。
上述操作代码如下
// 将a[i][j]这个格子赋值为c insert(i, j, i, j, c);
同理,以为差分也可以这样做,这里不再赘述,详见一维差分。
完整代码
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> #include <cmath> using namespace std; const int N = 1010; int a[N][N], b[N][N]; void insert(int i, int j, int x, int y, int c) { b[i][j] += c; b[i][y + 1] -= c; b[x + 1][j] -= c;; b[x + 1][y + 1] += c; } int main() { int n, m, q, x, y, xx, yy, c; scanf("%d%d%d", &n, &m, &q); for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { scanf("%d", &a[i][j]); } } // 初始化差分矩阵 for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { insert(i, j, i, j, a[i][j]); } } for (int i = 0; i < q; i ++ ) { scanf("%d%d%d%d%d", &x, &y, &xx, &yy, &c); insert(x, y, xx, yy, c); // 处理每个操作 } for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1]; // 二维前缀和,详见https://www.cnblogs.com/FXT1110011010OI/p/16549503.html } } for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { printf("%d ", b[i][j]); } printf("\n"); } return 0; }
这篇关于AcWing 798. 差分矩阵的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享