小a的轰炸游戏 （差分）

我是看题解的！

这道题还是有很多细节，当然，是一道差分的好题！

 

 

题意：有2种飞机，一种是只炸上半菱形，一种是炸整个菱形。问所有区域内的所有格子的异或和。

思路：用前缀和思路；

这样遍历过去就完成了一次轰炸。

但是，这样是不现实的，因为不可能每次都这样做。但是下面一下就可以。

这里，我尽量写清楚这道好题的主要思路。

也就是使用a, b,c,d4个数组来存储1和-1；然后再箭头方向更新！就很好了。

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const int maxn = 3e3 + 100, L = 1e3;
const int maxm = 1e5 + 100;
const ll INF = 1e16;
int a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn];
int n, m, k;

void up(int x, int y, int l){
    a[x - l / 2][y]++;    b[x - l / 2][y + 1]--;
    a[x + 1][y - l / 2 - 1]--; b[x + 1][y + l / 2 + 2]++;
}
void down(int x, int y, int l){
    c[x + 1][y - l / 2 + 1]++; d[x + 1][y + l / 2]--;
    c[x + l / 2 + 1][y + 1]--; d[x + l / 2 + 1][y]++;
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 0, op, x, y, l; i < k; ++i){
        scanf("%d%d%d%d", &op, &x, &y, &l);
        x += L;    y += L;
        up(x, y, l);
        if (op == 1)down(x, y, l);
    }
    int res = 0;
    for (int i = 0; i < n + 2 * L; ++i)
    {
        int ans = 0;
        for (int j = 0; j < m + 2 * L; ++j){
            ans += a[i][j] + b[i][j] + c[i][j] + d[i][j];
            if (i >= L + 1 && i <= L + n&&j >= L + 1 && j <= L + m)res ^= ans;
            a[i + 1][j - 1] += a[i][j];
            b[i + 1][j + 1] += b[i][j];
            c[i + 1][j + 1] += c[i][j];
            d[i + 1][j - 1] += d[i][j];
        }
    }
    cout << res << endl;
}