798. 差分矩阵

港控/mmm° 2023-09-30 12:32 30阅读 0赞

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

#include<iostream>
    
    using namespace std;
    
    const int N=1e6+10;
    int n,m;
    int a[N],b[N];
    
    void insert(int l,int r,int c){
        
        b[l]+=c;
        b[r+1]-=c;
    }
    
    int main(){
        
        scanf("%d%d",&n,&m);
        for(int i = 1;i<=n;i++) scanf("%d",&a[i]);
        
        for(int i=1;i<=n;i++) insert(i,i,a[i]);
        
        while(m--){
        
            int l,r,c;
            scanf("%d%d%d",&l,&r,&c);
            insert(l,r,c);
        }
        
        for(int i=1;i<=n;i++) b[i]+=b[i-1];
        for(int i=1;i<=n;i++) printf("%d ",b[i]);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，30人围观）

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

相关阅读

相关【算法| 差分 No.1】AcWing 797. 差分 & AcWing 798. 差分矩阵

【算法| 差分 No.1】AcWing 797. 差分 & AcWing 798. 差分矩阵

墨蓝/ 2024年04月27日 06:57/ 0 赞/ 101 阅读

相关一、基础算法5：前缀和与差分模板题+算法模板（前缀和，子矩阵的和，差分，差分矩阵）

文章目录算法模板前缀和模板子矩阵的和模板差分模板差分矩阵模板模板题前缀和

左手的ㄟ右手/ 2023年10月08日 23:25/ 0 赞/ 71 阅读

相关 798. 差分矩阵

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

港控/mmm°/ 2023年09月30日 12:32/ 0 赞/ 31 阅读

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

前缀和与差分 AcWing 798. 差分矩阵原题链接 [AcWing 798. 差分矩阵][AcWing 798.] 算法标签差分思路 ![

淩亂°似流年/ 2023年09月28日 11:16/ 0 赞/ 60 阅读

相关对称矩阵、方阵、逆矩阵、协方差矩阵、协方差

![20191009191333910.png][][日萌社][Link 1] [人工智能AI：Keras PyTorch MXNet TensorFlow Paddle

一时失言乱红尘/ 2023年07月07日 12:31/ 0 赞/ 43 阅读

相关协方差矩阵

一、统计学的基本概念统计学里最基本的概念就是样本的均值、方差、标准差。首先，我们给定一个含有n个样本的集合，下面给出这些概念的公式描述：均值：[![clip\_im

你的名字/ 2022年09月24日 11:28/ 0 赞/ 242 阅读

相关差分差分差分

class Solution { public: / 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可返回m天后

我不是女神ヾ/ 2022年08月31日 02:15/ 0 赞/ 315 阅读

相关协方差矩阵

[ ][Link 1] 一、统计学的基本概念统计学里最基本的概念就是样本的均值、方差、标准差。首先，我们给定一个含有n个样本的集合，下面给出这些概念的公式描述：

ゞ浴缸里的玫瑰/ 2022年05月23日 06:54/ 0 赞/ 229 阅读

相关差分

概念对于一个数组a\[n\]，有m次操作，都是对区间\[l,r\]加上k，完事后输出数组在知道第一个数a\[1\]的情况下，如果我们知道后面的数与前一个数的差值p，

我不是女神ヾ/ 2021年11月01日 10:04/ 0 赞/ 393 阅读

相关 AcWing 798. 差分矩阵【 c++详细题解】

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

矫情吗；*/ 2021年07月24日 22:28/ 0 赞/ 471 阅读