基础算法--差分

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

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

相关阅读

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

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

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

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

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

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

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

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

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

相关差分差分差分

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

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

相关【基础练习】【差分】codevs1242 布局题解

题目描述 Description 当排队等候喂食时，奶牛喜欢和它们的朋友站得靠近些。FJ有N（2<=N<=1000）头奶牛，编号从1到N，沿一条直线站着等候喂食。奶牛排在队伍

青旅半醒/ 2022年08月09日 17:40/ 0 赞/ 145 阅读

相关用python3实现差分进化算法（DE）

【注】：完整源码在我的[github][]上，找不找得到就看自己咯 ^ \_ ^ 差分进化算法(Differential Evolution Algorithm，DE)是一种

妖狐艹你老母/ 2022年05月24日 03:26/ 0 赞/ 481 阅读

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

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

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

相关基础算法--差分

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

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

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

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

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

相关差分

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

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