二维差分

C++ 代码

#include <iostream>
using namespace std;
const int N = 2010;

int d[N][N];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);

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

        d[x1][y1] ++;
        d[x1][y2 + 1] --;
        d[x2 + 1][y1] --;
        d[x2 + 1][y2 + 1] ++;
    }

    //原数组a[N][N] 是差分数组的前缀和
    //所以有d[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
    //所以有a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + d[i][j];

    for(int i = 1; i <=n; i ++)
    {
        for(int j = 1; j <=n; j ++)
        {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];// 差分数组求和->破坏 并变为原数组  避免了开一个新数组(适合不需要原数组的题)
            if(d[i][j] % 2 == 0) printf("0");
            else printf("1"); //使用if else 运行速度特别快(不知道为什么)
        }
        puts("");
    }


    return 0;
}