基础算法--差分

谁践踏了优雅 2021-12-03 16:11 313阅读 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

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    int main(void){
        int n,m;
        cin>>n>>m;
        vector<int>f(n);
        for(int i=0;i<n;i++)cin>>f[i];
        vector<int>d(n);
        d[0]=f[0];
        for(int i=1;i<n;i++)d[i]=f[i]-f[i-1];
        while(m--){
            int l,r,c;
            cin>>l>>r>>c;
            d[l-1]+=c;
            if(r<n)d[r]-=c;
        }
        for(int i=1;i<n;i++)d[i]+=d[i-1];
        for(int i=0;i<n;i++)cout<<d[i]<<' ';
        return 0;
    }

转载于:https://www.cnblogs.com/programyang/p/11152915.html

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关蓝桥杯一维差分 | 算法基础

亲爱的友友们，我们今天来学习一个简单而又常用的算法（比赛中遇到了就赚大发了额?）这个算法的名字就叫做差分算法差分算法在各种算法比赛中使用到的频率还是不低的，大家一定要掌握...

蔚落/ 2024年04月20日 07:37/ 0 赞/ 74 阅读

相关 Java之差分算法

目录一.差分 1.什么是差分 2.差分数组所解决的问题 3.差分解题的步骤 4.举例差分解题二.小明的彩灯 1.题目描述题目描述输入描述输出描述

小鱼儿/ 2024年03月26日 12:50/ 0 赞/ 78 阅读

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

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

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

相关 java生成差分文件_Android开发使用差分算法实现增量更新

还是老样子先上效果图，由于上传图片限制压缩有点严重凑合看吧： ![633c6742672537749d8f2cc055ad935e.gif][] 首先使用差分算法bsdif

傷城~/ 2022年11月10日 00:53/ 0 赞/ 351 阅读

相关【算法与数据结构】——前缀和，差分

参考博客[二维差分][Link 1] [差分——（2）二维差分][2] 前缀和给定一个数组a,如果有一个数组p，p\[i\] = p\[i-1\]+a\[i\]，

柔光的暖阳◎/ 2022年09月11日 03:18/ 0 赞/ 260 阅读

相关差分差分差分

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

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

相关前缀和与差分算法详解

1 . 前缀和其实可以把它理解为数学上的数列的前n项和（对于一个一维数组的前缀和）。我们定义对于一个数组a的前缀和数组s，s\[i\] = a\[1\]+a\[2\]+

「爱情、让人受尽委屈。」/ 2022年03月08日 07:05/ 0 赞/ 216 阅读

相关基础算法--差分

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

谁践踏了优雅/ 2021年12月03日 16:11/ 0 赞/ 314 阅读

相关差分

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

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