呼和浩特 网站建设石家庄今天最新新闻头条

标准差分模板   差分——前缀和的逆运算（一维+二维）-CSDN博客

题目

小蓝拥有 n×n 大小的棋盘，一开始棋盘上全都是白子。

小蓝进行了 m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色，黑色棋子变为白色)。

请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式

输入的第一行包含两个整数 n,m，用一个空格分隔，表示棋盘大小与操作数。

接下来 m 行每行包含四个整数 x1,y1,x2,y2，相邻整数之间使用一个空格分隔，表示将在 x1 至 x2 行和 y1 至 y2 列中的棋子颜色取反。

输出格式

输出 n 行，每行 n 个 0 或 1 表示该位置棋子的颜色。

如果是白色则输出 0，否则输出 1。

数据范围

对于 30% 的评测用例，1≤n,m≤500；
对于所有评测用例，1≤n,m≤2000，1≤x1≤x2≤n，1≤y1≤y2≤n。

输入样例：

3 3
1 1 2 2
2 2 3 3
1 1 3 3

输出样例：

001
010
100

方法

        针对于改变一个区间的值进行改变，（无论是加，减等），都可以考虑使用差分来做。

差分定义：给定一个原数组，构造一个差分数组，                        使得。

        因此，这里可以选用二维差分：

         差分——前缀和的逆运算（一维+二维）-CSDN博客   （对差分的详解）

        对于该题来说，可以发现，翻奇数次是黑子，翻偶数次是白子。因此如果我们想要改变某个区间的值 ，我们可以直接选择对于该区间的每个数+1，如果最终结果是偶数，就用0表示，奇数用1表示。

代码

import java.io.*;
// 直接+1，如果是偶数，则为白子，否则为黑子
class Main{static int N = 2010;static int n,m;static int[][] a = new int[N][N];public static void main(String[] args) throws IOException{BufferedReader in = new BufferedReader(new InputStreamReader(System.in));BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));String[] s = in.readLine().split(" ");n = Integer.parseInt(s[0]);m = Integer.parseInt(s[1]);while(m-->0){s = in.readLine().split(" ");int x1 = Integer.parseInt(s[0]);int y1 = Integer.parseInt(s[1]);int x2 = Integer.parseInt(s[2]);int y2 = Integer.parseInt(s[3]);insert(x1,y1,x2,y2); // 对每个区间进行差分}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+a[i][j]; // 计算前缀和，即a[i][j]if(a[i][j]%2==0) out.write("0");else out.write("1");}out.write("\n");}out.close();}// 差分计算public static void insert(int x1,int y1,int x2,int y2){a[x1][y1] += 1;a[x1][y2+1] -= 1;a[x2+1][y1] -= 1;a[x2+1][y2+1] += 1;}
}