AcWing 797. 差分(JAVA)
原题链接
简单
作者:
crayon不小心
,
2021-02-07 21:24:03
,
所有人可见
,
阅读 464
简易解释
import java.io.*;
public class Main {
static final int N = 1000010;
static int [] s = new int[N];//源数组
static int [] t = new int[N];//差分数组
static int n,m;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] split = reader.readLine().split(" ");
n = Integer.parseInt(split[0]);
m = Integer.parseInt(split[1]);
String [] str = reader.readLine().split(" ");
for (int i = 1; i <= n; i++) {
s[i] = Integer.parseInt(str[i - 1]);
}
//构造差分数组 t
//t[1] = s[1] - 0 = s[1]
//t[2] = s[2] - s[1]
//t[n] = s[n] - s[n -1]
/* sum all the t to get s[n]*/
//---> t[1]+t[2]+t[3]+...+t[n] = s[1] + (s[2] - s[1]) + (s[3] -s[2]) + ... (s[n] - s[n -1]) = s[n]
for (int i = 1; i <= n; i++) {
t[i] = s[i] - s[i -1];
}
/* t[l] + c = s[l] - s[l -1] + c
while it appends , t[l+1] = s[l+1] - s[l] , all t after a[l] expand c
--> s[l] = t[1] + t[2] + t[3] ...t[l] -->(t[l] plus c) -->s[l] = s[l] + c
t[r + 1] - c = s[r] - s[r- 1] - c
--> s[r + 1] = t[1] + t[2] + t[3] ... t[r + 1] = s[r +1] ( t[r + 1) minus c )
--> which means from t[r + 1] on ,all the t has minus c
sum all the t could cause all minus c after t[r + 1]
--> What means the place between l to r all plus c*/
while ( m-- > 0)
{
int l,r,c;
String [] st = reader.readLine().split(" ");
l = Integer.parseInt(st[0]);
r = Integer.parseInt(st[1]);
c = Integer.parseInt(st[2]);
t[l] += c;
t[r + 1] -= c;
}
for (int i = 1; i <= n; i++) {
t[i] += t[i-1]; //get the s[i] --> all the t before i to plus
writer.write(t[i]+" ");
}
writer.flush();
}
}