棋盘（寒假每日一题+二维差分）

题目

小蓝拥有?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

解题思路

? ? ? ? 该题目是一个典型的差分模板题，只要能够知道差分便可以轻松做出来。

注意：当我们求他的前缀和的时候，会出现大于2或者是小于0的一些数，只要这输出结果的时候&1便可，我们可以将其看成奇数和偶数的情况，2&1=0、1&1=1、-1%1=1……

源代码

#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

int g[N][N];
int n,m;

//二位差分的基本模板
void breach_dev(int x1,int y1,int x2,int y2){
    g[x1][y1]+=1,g[x2+1][y1]-=1,g[x1][y2+1]-=1,g[x2+1][y2+1]+=1;
}

int main()
{
    scanf("%d%d",&n,&m);
    
    while(m--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        
        breach_dev(x1,y1,x2,y2);
    }
    

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            g[i][j]=(g[i-1][j]+g[i][j-1]-g[i-1][j-1]+g[i][j]);       
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            printf("%d",g[i][j]&1);
        puts("");
    }
    return 0;
}