题目描述
输入一个长度为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
差分法
y总的代码不太好理解,用Java代码翻译一下如下
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] arr=br.readLine().split(" ");
int n=Integer.parseInt(arr[0]),m=Integer.parseInt(arr[1]);
//输入数组(前缀和数组)
int[] s=Arrays.asList(br.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();
int[] b=new int[n];
//差分数组的第0位与前缀和一致;
b[0]=s[0];
//计算差分数组,等同于y总的insert方法
for(int i=1;i<n;i++){
b[i]=s[i]-s[i-1];
}
while(m-- >0){
String[] t=br.readLine().split(" ");
int l=Integer.parseInt(t[0]),r=Integer.parseInt(t[1]),c=Integer.parseInt(t[2]);
//注意:由于本方法中的数组起始角标为0,所以l和r相当于已经加过1了
b[l-1]+=c;
if(r<n){
b[r]-=c;
}
}
//将差分数组转换为前缀和数组并输出
for(int i=0;i<n;i++){
if(i>0){
b[i]+=b[i-1];
}
System.out.print(b[i]+" ");
}
}
}