问题描述

小蓝拥有 $n \times n$ 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 $m$ 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反（也就是白色棋子变为黑色，黑色棋子变为白色）。请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式

输入的第一行包含两个整数 $n, m$，用一个空格分隔，表示棋盘大小与操作数。
接下来 $m$ 行每行包含四个整数 $x_1, y_1, x_2, y_2$，相邻整数之间使用一个空格分隔，表示将在 $x_1$ 至 $x_2$ 行和 $y_1$ 至 $y_2$ 列中的棋子颜色取反。

输出格式

输出 $n$ 行，每行 $n$ 个 0 或 1 表示该位置棋子的颜色。如果是白色则输出 0，否则输出 1。

样例输入

Plaintext

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

样例输出

Plaintext

001
010
100

评测用例规模与约定

对于 30% 的评测用例， $n, m \le 500$；
对于所有评测用例， $1 \le n, m \le 2000$，$1 \le x_1 \le x_2 \le n$，$1 \le y_1 \le y_2 \le m$。

二维异或差分,每次取反就相当于异或1

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>arr(n+2,vector<int>(n+2,0));
    for(int i=1;i<=m;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        arr[x1][y1]^=1,arr[x1][y2+1]^=1;
        arr[x2+1][y1]^=1,arr[x2+1][y2+1]^=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        arr[i][j]^=arr[i][j-1];
    }
      for(int i=1;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        arr[j][i]^=arr[j-1][i];
    }
       for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        cout<<arr[i][j];
        cout<<endl;
    }
}