基础算法--差分

谁践踏了优雅 2021-12-03 16:11 336阅读 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 条评论，336人围观）

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

相关阅读

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

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

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

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

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

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

相关 Java之差分算法

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

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

相关遗传算法与差分进化算法总结比较

遗传算法遗传算法的基本原理：遗传算法是一种基于生物进化原理构想出来的搜索最优解的仿生算法，它是模拟基因重组与进化的自然过程，把待解决问题的参数编成二进

深碍√TFBOYSˉ_/ 2023年10月17日 10:08/ 0 赞/ 24 阅读

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

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

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

相关算法设计 - 前缀和 & 差分数列

一维数组前缀和的概念前缀和的概念很简单，我们用一维数组的前缀和来举例，有如下一维数组： > arr = \[1, 2, 3, 4, 5\] 该数组的前缀和数组如下

川长思鸟来/ 2023年09月24日 17:34/ 0 赞/ 36 阅读

相关差分差分差分

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

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

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

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

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

相关基础算法--差分

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

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

相关差分

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

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