Y总模板(java)
import java.util.Scanner;
/**
* no.797
* 差分
*/
public class Main13 {
public static final int N = 100010;
public static int[] b = new int[N];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[] a = new int[N];
for (int i = 1; i <= n; i++){
a[i] = in.nextInt();
}
for (int i = 1; i <= n; i++){
insert(i, i, a[i]);
}
while (m-- != 0){
int l = in.nextInt(), r = in.nextInt();
int c = in.nextInt();
insert(l, r, c);
}
for (int i = 1; i <= n; i++){
b[i] += b[i - 1];
}
for (int i = 1; i <= n; i++){
System.out.print(b[i] + " ");
}
}
public static void insert(int i, int j, int c){
b[i] += c;
b[j + 1] -= c;
}
}
/** 首先搞清楚何为差分,差分就是相邻两个数据的差值,此时可以得到一个 b[i]数组
* 有两种理解方式,第一种理解方式:
* insert(i, i, a[i]); 该语句带入进去后的得到的是 b[1] = a[1] - a[0](值为 0); b[2] = a[2] - a[1]; b[3] = a[3] - a[2];
* 所以我要得到 a[3] 本质上就是 a[3] = b[1] + b[2] + b[3] = a[1] - a[1] + a[2] - a[2] + a[3];(数学里面经常用到这种思想)
* 第二种理解方式:
* 在未进行赋值语句之前,a[i] 和 b[i] 都是 0值,此时b[i] 就已经是 a[i]的差分数组了,因为所有元素都是0,所以差值自然都为 0;
* 所以直接使用y总的思想,等价于对赋值后的每一个 a[i] 我都进行一个 insert(i, i, a[i]); 操作,本质上就是更新 b[i],使得 b[i] 依旧是他的差分数组
* (等于进行了 insert(l, r, c);)这一步操作; 毕竟 a[i] = b[i] + b[i -1] + b[i-2] +...+b[1];
*/
差分模板(简化)
import java.util.Scanner;
/**
* no.797
* 差分
*/
public class Main13{
public static final int N = 100010;
public static int[] b = new int[N];
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[] a = new int[N];
for (int i = 1; i <= n; i++){
a[i] = in.nextInt();
insert(i, i, a[i]);
}
while (m-- != 0){
int l = in.nextInt(), r = in.nextInt(), c = in.nextInt();
insert(l, r, c);
}
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;
b[r + 1] -= c;
}
}
/** 首先搞清楚何为差分,差分就是相邻两个数据的差值,此时可以得到一个 b[i]数组
* 有两种理解方式,第一种理解方式:
* insert(i, i, a[i]); 该语句带入进去后的得到的是 b[1] = a[1] - a[0](值为 0); b[2] = a[2] - a[1]; b[3] = a[3] - a[2];
* 所以我要得到 a[3] 本质上就是 a[3] = b[1] + b[2] + b[3] = a[1] - a[1] + a[2] - a[2] + a[3];(数学里面经常用到这种思想)
* 第二种理解方式:
* 在未进行赋值语句之前,a[i] 和 b[i] 都是 0值,此时b[i] 就已经是 a[i]的差分数组了,因为所有元素都是0,所以差值自然都为 0;
* 所以直接使用y总的思想,等价于对赋值后的每一个 a[i] 我都进行一个 insert(i, i, a[i]); 操作,本质上就是更新 b[i],使得 b[i] 依旧是他的差分数组
* (等于进行了 insert(l, r, c);)这一步操作; 毕竟 a[i] = b[i] + b[i -1] + b[i-2] +...+b[1];
*/