差分矩阵 (板子题)

举报
irrational 发表于 2022/01/18 00:02:52 2022/01/18
【摘要】 输入一个 n 行 m 列的整数矩阵,再输入 q 个操作,每个操作包含五个整数 x1,y1,x2,y2,c,其中 (x1,y1) 和 (x2,y2)表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包含整数 n,m,q。 接下来 n...

输入一个 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

输入样例:


  
  1. 3 4 3
  2. 1 2 2 1
  3. 3 2 2 1
  4. 1 1 1 1
  5. 1 1 2 2 1
  6. 1 3 2 3 2
  7. 3 1 3 4 1

输出样例:


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

// 二维差分
// 给以(x1, y1)为左上角,(x2, y2)为右下角的子矩阵中的所有元素加上c:
// S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c


  
  1. #include <iostream>
  2. using namespace std;
  3. const int N = 1010;
  4. int n, m, q;
  5. int a[N][N], b[N][N];
  6. void insert(int x1, int y1, int x2, int y2, int c)
  7. {
  8. b[x1][y1] += c;
  9. b[x2 + 1][y1] -= c;
  10. b[x1][y2 + 1] -= c;
  11. b[x2 + 1][y2 + 1] += c;
  12. }
  13. int main()
  14. {
  15. scanf("%d%d%d", &n, &m, &q);
  16. for (int i = 1; i <= n; i ++ )
  17. for (int j = 1; j <= m; j ++ )
  18. scanf("%d", &a[i][j]);
  19. for (int i = 1; i <= n; i ++ )
  20. for (int j = 1; j <= m; j ++ )
  21. insert(i, j, i, j, a[i][j]);
  22. while (q -- )
  23. {
  24. int x1, y1, x2, y2, c;
  25. cin >> x1 >> y1 >> x2 >> y2 >> c;
  26. insert(x1, y1, x2, y2, c);
  27. }
  28. for (int i = 1; i <= n; i ++ )
  29. for (int j = 1; j <= m; j ++ )
  30. b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
  31. for (int i = 1; i <= n; i ++ )
  32. {
  33. for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);
  34. puts("");
  35. }
  36. return 0;
  37. }

两个重点


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

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];

文章来源: blog.csdn.net,作者:irrationality,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/weixin_54227557/article/details/120595640

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。