二维差分
题目描述
输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,
其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上 c。
请你将进行完所有操作后的矩阵输出。
输入格式
第一行包含整数 n,m,q。
接下来 n 行,每行包含 m 个整数,表示整数矩阵。
接下来 q 行,每行包含 5 个整数 x1,y1,x2,y2,c,表示一个操作。
输出格式
共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。
数据范围
1≤n,m≤1000, 1≤q≤100000, 1≤x1≤x2≤n, 1≤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
思路分析
暴力写法
首先就是数据的读入了,定义一个 n, m, q 然后读入这三个数据,接下来就是一个 n * m 的 循环,给初始矩阵读入
在接下来就是 q 次循环,进行 q 次操作,最后就是给操作后的矩阵输出出来就好了
暴力写法的话,具体该怎么操作呢,既然都暴力了,就没必要算法风度,直接模拟出来这个过程就好了
在 q 次循环当中,定义 x1, y1, x2, y2, c然后给这几个数据读入,设置一个两层循环,这两层循环的循环范围
分别是 x1 ~ x2 和 y1 ~ y2,然后就是给每一项数据加上一个常数 c 就好了,q 次循环过后,输出矩阵就好了,
好,上暴力代码
#include <iostream>
using namespace std;
const int N = 1000;
int a[N][N];
int main(){
int n, m, q;
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 k = 1; k <= q; k ++){
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
for (int i = x1; i <= x2; i ++)
for (int j = y1; j <= y2; j ++)
a[i][j] += c;
}
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++)
printf("%d ", a[i][j]);
printf("\n");
}
return 0;
}
时间复杂度分析
时间复杂度貌似成了我的尿性了,所以此处加个标题来尊重一下,哈哈,没错哈,暴力写法还是会超时哈
时间复杂度分析一波,循环层数最多是三层循环哈, 然后 q 的取值范围是 100000,x2 和 x1 以及 y2 和 y1的
最大差值都是可以达到 1000 的,所以最坏时间复杂度是 10 的 十一 次方(应该没算错,我是掰着手指头和脚趾头数的),
大于 10 的八次方,所以近乎百分百会超时,ok ,下一步
优化写法
首先有个疑问,我们是否可以像一维差分那样,做一个优化呢,答案当然是可以的哈,一维差分的优化,就像是给前面的
指定位置倒上一堆土(加上个常数 c),然后再后面的指定位置挖去一堆土 (减去个常数c)然后再经过前缀和处理
只有中间部分受影响,两端的部分不受影响对吧
那么,二维差分该如何做呢,现在我们就是想做到,只在指定的位置加上或者减去一个常数 c ,然后经过前缀和处理后,只让指定区域内的项
受到影响,区域外的项不受影响对吧
如何做到,这个问题的核心,现在就是找到这几个指定位置对吧,两点确定一条直线,这没啥好说的,三个点确定一个平面
这也没啥好说的,但是如何确定一个唯一的一个四条边的矩阵,我们至少的需要四个点对吧,但是至多需要几个,几个呢,不晓得
不用管(不然不好一本正经忽悠下去了)
我们现在假设 二维数组 a 用来这个矩阵中的元素,再开一个 二维数组 s 来进行 操作的存储,
假如说,我们现在只有两个点( 每一个方格代表 s[i][j],由于是全局变量,初值都是 0)
其中在 紫色斜线区域 上 加上一个常数 c ,在 蓝色斜线区域 上 减去一个常数 c,然后我们进行一个前缀和处理
如果现在我们只考虑红色线段以上的部分,我么可以发现,只有圈圈的部分的前缀和受到了我们刚刚进行的操作的影响,
但是其他部分是不受影响的对吧
如果我们现在只考虑绿色线段左边的部分,我们发现,相较于红色线段上面的部分,多出来了好多圈圈的部分对吧,
但是,只有在蓝色线框内的圆圈,是我们所期望的,但是绿色线段左边部分,明显有很多圈圈是我们所不期望出现的
这时候,我们是否可以再通过设置一个点,来堵住这个或者限制这个影响的区域呢,答案是肯定的,这个点在哪儿,
我想已经不用多说了,直接上图
然后再经过前缀和处理之后,是不是就成了这个样子了,看下图
然后我们已经完成了我们的操作,直接 把 a[i][j] + s[i][j] 输出就好了,对吧,
但是,我们前面说了,我们需要至少四个点才能确定一个唯一的四边形对吧,怎么三个点就行了,是不是判断错了,不是的哈
其实上面这张图并不完善,也就是说,还有其他点,收到了影响,而且是预期范围之外的,这部分就是橘色记号标注的区域
然后我们仍然是可以通过一个点来给那个预期之外的影响给堵住的哈,想必已经可以很明显的看出来是哪个点,直接上终极图
但是这里别杠哈,不要说,在坐标纸上,我通过一个左上角坐标和一个右下角坐标,或者我通过一个右上角坐标和一个左下角坐标
确定一个矩阵哈,如果说我们就这么认为,可以就通过上述两个点,确定那个矩阵的话,会有什么影响呢,这里画了个图,作为最后的补充
橘黄色线框内圈圈的部分是我们所期望的,其他圈圈的部分都不是我们所期望的,所以我们不能通过两个角的坐标来确定这个矩阵
好了,时间也不早了,上代码
#include <iostream>
using namespace std;
const int N = 1010;
int a[N][N], s[N][N];
int main(){
int n, m, q;
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 k = 1; k <= q; k ++){
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++)
printf("%d ", a[i][j] + s[i][j]);
printf("\n");
}
return 0;
}
这里的核心操作主要是这一部分哈,在这里着重强调一下
for (int k = 1; k <= q; k ++){
int x1, y1, x2, y2, c;
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
s[x1][y1] += c;
s[x1][y2 + 1] -= c;
s[x2 + 1][y1] -= c;
s[x2 + 1][y2 + 1] += c;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
时间复杂度分析
这里再整一个把,之前的最坏时间复杂度是 10 的 十一 次方,现在这个我看着,最多也就是 10 的六次方了好像
所以不用担心超时的事儿了