797. 差分(有图解)

素颜马尾好姑娘i 2023-09-30 12:16 14阅读 0赞

输入一个长度为 n 的整数序列。

接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 \[l,r\] 之间的每个数加上 c。

请你输出进行完所有操作后的序列。

输入格式  
第一行包含两个整数 n 和 m。

第二行包含 n 个整数，表示整数序列。

接下来 m 行，每行包含三个整数 l，r，c，表示一个操作。

输出格式  
共一行，包含 n 个整数，表示最终序列。

数据范围  
1≤n,m≤100000,  
1≤l≤r≤n,  
−1000≤c≤1000,  
−1000≤整数序列中元素的值≤1000

输入样例：
    6 3
    1 2 2 1 2 1
    1 3 1
    3 5 1
    1 6 1
    输出样例：
    3 4 5 3 4 2

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]

#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;
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5LiD5a-75YyX6YeM_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/3174a785a63142dcafc37346c2ab210c.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5LiD5a-75YyX6YeM,size_20,color_FFFFFF,t_70,g_se,x_16

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关差分放大电路公式有哪些

差分放大电路公式有：A = (1 + R2 / R1) × (1 + R4 / R3)，Av = A × (1 + R6 / R5)，Vo = Av × Vi，Vi = Vo

╰半夏微凉°/ 2024年03月25日 12:44/ 0 赞/ 94 阅读

相关 797. 差分(有图解)

输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 \[l,r\] 之间的每个数加上 c。请你输出进行完所有操作后的

素颜马尾好姑娘i/ 2023年09月30日 12:16/ 0 赞/ 15 阅读

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

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

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

相关 AcWing-797. 差分刷题笔记（c++）

写在前面难度：简单知识盲点，学习新的算法思想相关文章很多，不再赘述题目详情输入一个长度为n的整数序列。

浅浅的花香味﹌/ 2023年02月25日 10:20/ 0 赞/ 18 阅读

相关 AcWing 797 差分一维差分 c/c++实现

原题链接：[AcWing 797 差分][AcWing 797] > 题目描述：给出 n 个整数和 m 个操作，每个操作输入三个数 l、r、v，表示将区间 \[l,r\] 中

你的名字/ 2022年12月22日 04:38/ 0 赞/ 198 阅读

相关一阶差分与二阶差分及还原

一阶差分与二阶差分及还原一阶差分 arr = np.arange(10) np.random.shuffle(arr) arr = pd.

比眉伴天荒/ 2022年10月06日 11:53/ 0 赞/ 612 阅读

相关差分差分差分

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

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

相关【2019.7.10】树上差分杂[LCA 倍增][树上差分点差分边差分]

多用于记录树上节点被经过的次数,记录某条边被经过的次数的时候点差分 [P3128 \[USACO15DEC\]最大流Max Flow][P3128_ _US

迷南。/ 2021年11月17日 15:44/ 0 赞/ 340 阅读

相关差分

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

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