题目描述
输入一个长度为 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
差分
1.构造
对于一个给定数组a[n],我们构造它的差分数组b[n]
令 b[i] = a[i] - a[i - 1]
此时的a[n]叫做b[n]的前缀和数组,b[n]为a[n]的差分数组
2.作用
给定一数组 a[n] ,在其区间 [l,r] 之间的每个元素都加上 c ,如果此操作进行m次,则时间复杂度为 O(n*m)
但是如果构造一个 a[n] 的差分数组 b[n],因为对于数组 a[n] 来说,[l,r] 之间的元素都包含了b[l]这个元素
因此只对 b[l] 进行 +c 一次操作就能满足对 a[l]-a[r] 之间的元素进行 +c 的操作
对于 a[r] 之后的元素,因为也包含了b[l],所以多加了 c,所以对 b[r + 1] 进行 -c 操作就可以了
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/*
差分
*/
public class Main {
public static void main(String[] args) throws IOException {
//输入序列元素个数 n 和操作次数 m
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s0 = br.readLine().split(" ");
int n = Integer.parseInt(s0[0]);
int m = Integer.parseInt(s0[1]);
//定义初始数组a[n]
int N = 1000010;
int[] a = new int[N];
String[] s1 = br.readLine().split(" ");
for (int i = 1, t = 0; i <= n; i++, t++) {
a[i] = Integer.parseInt(s1[t]);
}
//构造差分数组b[n]
int[] b = new int[N];
for (int i = 1; i <= n; i++) {
b[i] = a[i] - a[i - 1];
}
//对差分数组进行操作
while (m-- > 0) {
String[] s2 = br.readLine().split(" ");
int l = Integer.parseInt(s2[0]);
int r = Integer.parseInt(s2[1]);
int c = Integer.parseInt(s2[2]);
b[l] += c;
b[r + 1] -= c;
}
//计算并输出操作后的数组 a[n]
for (int i = 1; i <= n; i++) {
a[i] = a[i - 1] + b[i];
System.out.print(a[i] + " ");
}
}
}