二维差分
-
这一题运用到了二维差分的概念,由前缀和数组求差分数组之后,然后再对差分数组进行更新
而且由此可以引申出,前缀和数组可以是由 所有元素都为0的数组,进行n*m次更新的结果 -
而且本题因为数据量过大,jaca的scanner输入数据过慢,system.out,输出数据也太慢,所以可以采用快读来进行输入输出
- 或者不用快读,但是把所有答案录入一个StringBulider中进行输出
- 下面是我的代码,关键地方我会加上注释,如果写的不够清楚可以留言
StringBulider输出
import java.util.Scanner;
/**
* 边界处理,一定要数组设置的比原来的空间>= 2
* @author 18176
*
*/
public class 二维差分_差分矩阵 {
static int s[][];
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int q=sc.nextInt();
int a[][]=new int [n+10][m+10];
s=new int [n+10][m+10];//static ,设置空间+10,是后面更新操作的需要,需要进行边界处理
//而且相较于c,java可以直接设置空间,一般都是输入了空间待笑傲,然后设置空间
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
a[i][j]=sc.nextInt();//不需要设置
insert(i,j,i,j,a[i][j]);
//将差分数组看成元素都为0的数组,然后每次输入前缀和数据都是对差分数组进行数据的更新操作
}
}
while(q--!=0) {
int x1=sc.nextInt();
int y1=sc.nextInt();
int x2=sc.nextInt();
int y2=sc.nextInt();
int c=sc.nextInt();
insert(x1,y1,x2,y2,c);//更新数据
}
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
//求前缀和
}
}
StringBuilder st=new StringBuilder();
//用StringBuilder,是因为其进行字符串操作快
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
st.append(s[i][j]).append(' ');
}
st.append('\n');//换行
}
System.out.print(st);
}
private static void insert( int x1, int y1, int x2, int y2, int t) {
s[x1][y1]+=t;
s[x2+1][y1]-=t;
s[x1][y2+1]-=t;
s[x2+1][y2+1]+=t;
}
}
IO_字符流输入呼出
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class 二维差分_差分矩阵_快排 {
static int sum[][];
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
String s[]=br.readLine().split(" ");
//redLine直接读取一行,包括空格,需要split分割
int n=Integer.parseInt(s[0]);
int m=Integer.parseInt(s[1]);
int q=Integer.parseInt(s[2]);
sum=new int [n+10][m+10];
for (int i = 1; i <=n; i++) {
String z[]=br.readLine().split(" ");
for (int j = 0; j < z.length; j++) {
insert(i,j+1,i,j+1,Integer.parseInt(z[j]));
//更新数据
}
}
while(q--!=0) {
String z[]=br.readLine().split(" ");
int t[]=new int [5];
for (int i = 0; i < t.length; i++) {
t[i]=Integer.parseInt(z[i]);
}
insert(t[0], t[1], t[2], t[3], t[4]);
}
for (int i = 1; i <=n; i++) {
for (int j = 1; j <=m; j++) {
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
bw.write(sum[i][j]+" ");//输出数据
}
bw.write("\n");//换行
}
bw.flush();
bw.close();
br.close();
//分别是刷新,关闭录入,关闭读取
}
private static void insert(int x1, int y1, int x2, int y2, int c) {
sum[x1][y1]+=c;
sum[x2+1][y1]-=c;
sum[x1][y2+1]-=c;
sum[x2+1][y2+1]+=c;
}
}
太强了大佬
诶嘿