前缀和与差分 AcWing 798. 差分矩阵

淩亂°似流年 2023-09-28 11:16 94阅读 0赞

前缀和与差分 AcWing 798. 差分矩阵

原题链接

AcWing 798. 差分矩阵

算法标签

差分

思路

在这里插入图片描述
改图转该题解

代码

  1. #include<bits/stdc++.h>
  2. #define int long long
  3. #define rep(i, a, b) for(int i=a;i<b;++i)
  4. #define Rep(i, a, b) for(int i=a;i>b;--i)
  5. using namespace std;
  6. const int N = 1005;
  7. int a[N][N],b[N][N];
  8. inline int read(){
  9.    int s=0,w=1;
  10.    char ch=getchar();
  11.    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
  12.    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
  13.    return s*w;
  14. }
  15. void put(int x) {
  16.     if(x<0) putchar('-'),x=-x;
  17.     if(x>=10) put(x/10);
  18.     putchar(x%10^48);
  19. }
  20. void insert(int x1, int y1, int x2, int y2, int c){
  21.     b[x1][y1]+=c;
  22.     b[x2+1][y1]-=c;
  23.     b[x1][y2+1]-=c;
  24.     b[x2+1][y2+1]+=c;
  25. }
  26. signed main(){
  27.     ios::sync_with_stdio(false);
  28.     cin.tie(0);
  29.     cout.tie(0);
  30.     int n=read(), m=read(), q=read();
  31.     rep(i, 1, n+1){
  32.         rep(j, 1, m+1){
  33.             a[i][j]=read();
  34.             // b数组初始化
  35.             insert(i, j, i, j, a[i][j]);
  36.         }
  37.     }
  38.     // 差分
  39.     while(q--){
  40.         int a=read(), b=read(), c=read(), d=read(), e=read();
  41.         insert(a, b, c, d, e);
  42.     }
  43.     // 最终矩阵
  44.     rep(i, 1, n+1){
  45.         rep(j, 1, m+1){
  46.             b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
  47.         }
  48.     }
  49.     rep(i, 1, n+1){
  50.         rep(j, 1, m+1){
  51.             printf("%lld ", b[i][j]);
  52.         }
  53.         puts("");
  54.     }
  55.     return 0;
  56. }

模板

  1. void insert(int x1, int y1, int x2, int y2, int c){
  2.     b[x1][y1]+=c;
  3.     b[x2+1][y1]-=c;
  4.     b[x1][y2+1]-=c;
  5.     b[x2+1][y2+1]+=c;
  6. }

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

    相关 前缀和差分

    前缀和： 前缀和是一种在数学和计算机科学中使用的概念。它指的是一个数组中每个元素之前(包括该元素)的所有元素的总和。 例如，对于数组 A = \[1, 2, 3, 4, 5

    水深无声水深无声/ 0 赞/ 100 阅读

    相关 798. 差分矩阵

    输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和

    港控/mmm°港控/mmm°/ 0 赞/ 65 阅读

    相关 差分 & 前缀和

    我们从问题入手。   入门问题：有已赋值的 n 个数，现在有 m 个指令 操作 1： 每一次要求将第 k 个数加上 a； 操作 2： 查询第 k 个数字的值。 $1 

    怼烎@怼烎@/ 0 赞/ 474 阅读