ZT21【模板】差分

描述

对于给定的长度为 n 的数组{a1​,a2​,…,an​} ，我们有 m 次修改操作，每一次操作给出三个参数 l,r,k ，代表将数组中的 al​,al+1​,…,ar​ 都加上 k 。

请你直接输出全部操作完成后的数组。

输入描述：

第一行输入两个整数 n,m(1≦n,m≦10^5) 代表数组中的元素数量、操作次数。

第二行输入 n 个整数 a1​,a2​,…,an​(−10^9≦ai​≦10^9) 代表初始数组。

此后 m 行，每行输入三个整数 l,r,k(1≦l≦r≦n; −10^9≦k≦10^9) 代表一次操作。

输出描述：

在一行上输出 n 个整数，代表全部操作完成后的数组。

示例1

输入：

3 2 1 2 3 1 2 4 3 3 -2

输出：

5 6 1 一、问题分析

首先读题，仔细看描述中的内容，发现需求是

1.给定一个长度为n的数组，以及m次操作

2.每次操作有三个参数l，r，k，代表将数组中的al到ar（l和r表示下标）全都加上k的值

3.求m次操作后的数组每一项的值

二、解题思路

1.首先读取数据到long long数组a

2.然后读取m次操作到一个dp数组

3.读取的方式是，将dp[l] += x;

然后将dp[r + 1] -= x;

4.之后遍历dp数组，dp[i] += dp[i - 1];

每一项等于前一项和本项和。

5.最后我们遍历两个数组，输出结果结果是原数组a[i]加上dp[i]数组（dp数组记录了所有的区间增加和减少）

三、具体步骤

使用的语言是C

#include <stdio.h> #define MAX_N 101010 #define ll long long ll a[MAX_N]; ll dp[MAX_N]; int main() { int n, m, i; scanf("%d%d", &n, &m); for (i = 1; i <= n; i++) { scanf("%lld", &a[i]); } for (i = 1; i <= m; i++) { int l, r, x; scanf("%d%d%d", &l, &r, &x); dp[l] += x; dp[r + 1] -= x; } for (i = 1; i <= n; i++) { dp[i] += dp[i - 1]; } for (i = 1; i <= n; i++) { printf("%lld ", a[i] + dp[i]); } return 0; }