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

你的名字 2022-12-22 04:38 203阅读 0赞

原题链接：[AcWing 797 差分][AcWing 797]

> 题目描述：给出 n 个整数和 m 个操作，每个操作输入三个数 l、r、v，表示将区间 \[l,r\] 中的每个数加上v。问最终数列中每个数是多少。  
> 1 ≤ n,m ≤ 100000,  
> 1≤ l ≤ r ≤ n,  
> −1000 ≤ c ≤ 1000,

> 输入样例：  
> 6 3  
> 1 2 2 1 2 1  
> 1 3 1  
> 3 5 1  
> 1 6 1

> 输出样例：  
> 3 4 5 3 4 2

**思路：** 这就是用一个差分数组快速的实现对一个区间的修改。我们用一个b数组（初始化为0）来记录，若对区间 \[l,r\] 加c，我们可以给b\[l\] + c，给b\[r+1\] - c，修改后的a\[i\]就是原数组的a\[i\]加上b数组1到i的和，[差分详见此处][Link 1]。  
证明如下：  
![yxcnb][]  
**ac代码：**

#include<iostream>
    using namespace std;
    const int N = 100010;
    
    int a[N],b[N],n,m,l,r,c;
    int main()
    { 
    	cin >> n >> m;
    	for(int i = 1;i <= n;i++)
    		cin >> a[i];
    	for(int i = 0;i < m;i++)
    	{ 
    		cin >> l >> r >> c;
    		b[l] += c;
    		b[r+1] -= c;
    	}
    	for(int i = 1;i <= n;i++)
    	{ 
    		b[i] += b[i-1];
    		cout << a[i]+b[i] << " ";
    	}
    
    	return 0;
    }

[AcWing 797]: https://www.acwing.com/problem/content/799/
[Link 1]: https://blog.csdn.net/qq_45735851/article/details/106535635
[yxcnb]: /images/20221120/040f29d2c9f2408f9f5e2e9d3b662a08.png

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 797. 差分(有图解)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关差分差分差分

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

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

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

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

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

相关差分

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

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

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

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

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