文登区城乡建设局网站,微信怎么做淘客网站,做音乐创作的网站,做网站公司凡科在了解差分之前#xff0c;我们首先需要知道前缀和的概念。
前缀和简单介绍#xff1a;
对于一个数组A#xff0c;要求出A[0]~A[i]的和#xff0c;我们通常的做法是遍历一边#xff0c;加起来。但是要求m组这样的和#xff0c;我们就要花费O(mn)的时间复杂度。显然不合…在了解差分之前我们首先需要知道前缀和的概念。
前缀和简单介绍
对于一个数组A要求出A[0]~A[i]的和我们通常的做法是遍历一边加起来。但是要求m组这样的和我们就要花费O(mn)的时间复杂度。显然不合理。所以我们要用到动态规划里的备忘录思想创建一个新数组B,B[i]记录的是B[0]~B[i]的和。这个数组就是A的前缀和。
差分的概念
有前缀和就有其逆定理。那就是假设数组A是一个前缀和数组那么怎么求原数组呢B答案是B[i] A[i] - A[i-1] 这很好理解。这种算法可以被视为前缀和的逆运算。
现在我们获得了差分的概念让我们看看怎么使用它吧。
如何使用
差分的主要用处在于
快速将序列A[l..r]的区间每个元素加上d。
正常加我们就需要不断遍历这一段数组。但是我们有了差分的概念因此我们可以得到差分数组B[l] A[l] d - A[l-1] B[l] d
B[r1] A[r1] -A[r] -d B[r1] - d
差分可以将在原序列上的 “区间操作” 转化为差分序列上的 “单点操作”。
现在有了对一维数组的差分运算 我们可以看看二维数组怎么操作。
二维差分
二维差分要解决的问题是给原二维数组A的[x1,y1]~[x2,y2]处的所有元素加上d。
我们根据几何关系可以得出以下公式
Bi,j Ai,j - Ai-1,j - Ai,j-1, Ai-1,j-1
结合前面文章中差分的用途可以容易的想到二维差分主要是用于快速将一个区块中的所有元素都加上 d。
根据我们的公式我们很快得出一个结论
对原数组A的[x1,y1]~[x2,y2]处的所有元素加上d等价于
B[x1,y1] 1
B[x1,y21] - 1
B[x21,y1] - 1
B[x21,y21] 1
可以画一张图自己看看推导很简单
应用
问题描述
小兰拥有n*n 大小的棋盘一开始棋盘上全是白子小兰进行了m 次操作每次操作会将棋盘上某个范围内的所有棋子的颜色取反也就是白色棋子变为黑色黑色棋子变为白色。请输出所有操作做完后棋盘上每个棋子的颜色。
输入格式 输入的第一行包含两个整数 n,m用一个空格分隔表示棋盘大小与操作数。
接下来 m 行每行包含四个整数 x1,y1,x2,y2相邻整数之间使用一个空格分隔表示将在 x1~x1行,y1~y2 列中的棋子颜色取反。
输出格式 输出 n 行每行 n 个 0 或 1 表示该位置棋子的颜色。如果是白色则输出 0否则1
样例输入
3 3
1 1 2 2
2 2 3 3
1 1 3 3
样例输出
001
010
100
代码
import java.util.Scanner;public class Main extends Base{public static void main(String[] args) {int n I(),m I();int[][] sum new int[n1][n1]; //原数组int[][] diff new int[n2][n2]; //差分数组for(int k0;km;k){int x1 I(),y1 I(),x2 I(),y2 I();//每次对差分数组4个位置操作diff[x1][y1];diff[x1][y21]--;diff[x21][y1]--;diff[x21][y21];}//由差分数组得到原数组for(int i1;in;i){for(int j1;jn;j){sum[i][j] sum[i-1][j]sum[i][j-1]diff[i][j]-sum[i-1][j-1];if(sum[i][j]%20) print(0);else print(1);}print(\n);}}
}
class Base {static Scanner scan new Scanner(System.in);static int I(){return scan.nextInt();}static T void println(T x){System.out.println(x);}static T void print(T x){System.out.print(x);}
}
sum[i][j] sum[i-1][j]sum[i][j-1]diff[i][j]-sum[i-1][j-1];
这一行是
Bi,j Ai,j - Ai-1,j - Ai,j-1, Ai-1,j-1求Ai,j的运算变形
