import java.util.Scanner;
1、前缀和数列a;原数列b
2、原数列的第L项加C,第R+1项减C,则相应的前缀和数列的第L项到第R项每一项都加C;
3、相反,前缀和数列的第L项到第R项每一项都加C,则相应的原数列的第L项加C,第R+1项减C
4、题目要求:一个数列的第L项到第R项每一项都加C以后得到的数列?
5、题意可以理解为:将题目中要求的数列看作前缀和数列,求前缀和数列的第L项到第R项每一项都加C以后得到的数列;
6、那么就要先求已给数列的原数列,将原数列的第L项加C,第R+1项减C,再求处理后的原数列的前缀和数列,新的前缀和数列即为所求;
7、求已给数列的原数列可利用3中的分析:已知给定数列a
—原数列和前缀和的所有项都是0
—所有项为0的原数列b,第i项加a[i],第i+1项减a[i],则其前缀和的第i项为a[i],此操作后得到的b数列即为给定数列a的差分数列
—按照1中的分析:对b数列的第L项加C,第R+1项减C。此为对差分数列b进行操作
—求差分数列b的前缀和数列,即可求得相应的前缀和数列(a)的第L项到第R项每一项都加C
—遍历新数列a即为所求;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n+1];
2、---所有项为0的原数列b,第i项加a[i],第i+1项减a[i],则其前缀和的第i项为a[i],此操作后得到的b数列即为给定数列a的差分数列
for(int i=1;i<=n;i++){
a[i] = sc.nextInt();
insert(i,i,a[i]);
}
3、---按照1中的分析:对b数列的第L项加C,第R+1项减C,即可求得相应的前缀和数列(a)的第L项到第R项每一项都加C
while(m-- != 0){
int l=sc.nextInt();
int r=sc.nextInt();
int c=sc.nextInt();
insert(l,r,c);
}
4、---求差分数列b的前缀和数列,即可求得相应的前缀和数列(a)的第L项到第R项每一项都加C
int x = 0;
for(int i=1;i<=n;i++){
x = b[i]+x;
a[i] = x;
}
5、---遍历新数列a即为所求
for(int i=1;i<=n;i++){
System.out.print(a[i]+" ");
}
}
1、---原数列和前缀和的所有项都是0
static int[] b = new int[100010];
static void insert(int l,int r,int c){
b[l] = b[l] +c;
b[r+1] = b[r+1]-c;
}
}