题目描述
输入一个长度为 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, 2, 2, 1, 2, 1]。
将序列位置 1 到 3 的数都加 1:
原始序列 [1, 2, 2, 1, 2, 1]
在位置 1 到 3 分别加上 1,变成 [2, 3, 3, 1, 2, 1]
将序列位置 3 到 5 的数都加 1:
上一步得到的序列 [2, 3, 3, 1, 2, 1]
在位置 3 到 5 分别加上 1,变成 [2, 3, 4, 2, 3, 1]
将整个序列都加 1:
上一步得到的序列 [2, 3, 4, 2, 3, 1]
整个序列的每个位置都加上 1,变成 [3, 4, 5, 3, 4, 2]
这些步骤描述了对序列的每次操作,每次操作都是对特定区间的数进行加法操作,并最终得到了 [3, 4, 5, 3, 4, 2] 这个最终序列。
java代码
import java.util.Scanner;
public class Main {
static final int N = 100010; // 定义数组的最大长度
static int[] b = new int[N]; // 定义存储操作后结果的数组b
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 读取数组长度
int m = scanner.nextInt(); // 读取操作次数
int[] a = new int[N]; // 定义辅助数组a
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt(); // 读取初始数组a
insert(i, i, a[i]); // 进行一次单点更新操作
}
while (m-- > 0) {
int l, r, c;
l = scanner.nextInt(); // 读取操作区间左端点
r = scanner.nextInt(); // 读取操作区间右端点
c = scanner.nextInt(); // 读取操作值
insert(l, r, c); // 进行区间更新操作
}
scanner.close(); // 关闭Scanner
// 计算最终数组并输出结果
for (int i = 1; i <= n; i++) {
b[i] += b[i - 1]; // 累加得到最终结果
System.out.print(b[i]+" "); // 输出每个位置的结果
}
}
public static void insert(int l, int r, int c) {
b[l] += c; // 在l位置加上c
b[r + 1] -= c; // 在r+1位置减去c,保持更新操作的线性效果
}
}
过程模拟
读取数组:
输入的数组 a = [1, 2, 2, 1, 2, 1]
初始化存储累加增量的数组 b = [0, 0, 0, 0, 0, 0, 0]
单点更新:
单点更新 insert(1, 3, 1):在位置 1 到 3 加 1
b = [0, 1, 0, 0, -1, 0, 0]
区间更新:
区间更新 insert(3, 5, 1):在位置 3 到 5 加 1
b = [0, 1, 0, 1, -1, 0, 0]
再次区间更新:
区间更新 insert(1, 6, 1):在位置 1 到 6 加 1
b = [0, 2, 1, 2, -1, -1, 0]
计算最终结果:
按照累加规则得到最终结果:
b[1] = b[1] + b[0] = 2 + 0 = 2
b[2] = b[2] + b[1] = 1 + 2 = 3
b[3] = b[3] + b[2] = 2 + 3 = 5
b[4] = b[4] + b[3] = -1 + 5 = 4
b[5] = b[5] + b[4] = -1 + 4 = 3
b[6] = b[6] + b[5] = 0 + 3 = 3
最终结果为 3 4 5 3 4 2。