棋盘（二维差分）

题目：

5396. 棋盘

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

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

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

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

输入格式

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

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

输出格式

输出 nn 行，每行 nn 个 00 或 11 表示该位置棋子的颜色。

如果是白色则输出 00，否则输出 11。

数据范围

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

输入样例：

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

输出样例：

001
010
100

代码：

#include <bits/stdc++.h>
using namespace std;

const int N=2010;
int diff[N][N],a[N][N];
//a代表棋盘上的数组，即黑白0，1。开始时都为0（白）
//最终求得的差分数组是棋盘上该位置操作的数量。偶数为0，奇数为1
void insert(int x1,int y1,int x2,int y2,int c){
    diff[x1][y1]+=c;
    diff[x2+1][y1]-=c;
    diff[x1][y2+1]-=c;
    diff[x2+1][y2+1]+=c;
}

int main(){
    
    int n,m;
    cin>>n>>m;
    
    //求差分数组,因为a[i][j]都为0，所以直接插0就行
    //其实这部可以不用写
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            insert(i,j,i,j,0);
        }
    }
    
    
    while(m--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        //每一次对一个矩阵区间进行反转操作，理解为对该区间进行加1
        insert(x1,y1,x2,y2,1);
    }
    
    //求原数组,前缀和
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            diff[i][j]+=diff[i-1][j]+diff[i][j-1]-diff[i-1][j-1];
        }
    }
    //输出
     for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(diff[i][j]%2==0){//是偶数
               cout<<0;
            }else{
               cout<<1;
            }
        }
        cout<<"\n";
    }
    return 0;
}

判断奇偶可用&1,时间更快点 

 //输出
     for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<(diff[i][j]&1);
        }
        cout<<"\n";
    }

思路：

操作次数为奇数时最终该位置为黑色1，偶数次时，最终为白色0.根据此规律我们可以记录每次该位置的操作数，让此区域的数量都加1。

对某一矩阵区间进行操作，+1操作-->在此区间所有的数都加上一个1。可以考虑用二维差分来操作。insert(x1,y1,x2,y2,1)

最后让差分数组求和来求得操作后（相应区间的数+1）的数组。判断此数组中奇数和偶数的个数，来输出1/0。