我是看题解的!
这道题还是有很多细节,当然,是一道差分的好题!
题意:有2种飞机,一种是只炸上半菱形,一种是炸整个菱形。问所有区域内的所有格子的异或和。
思路:用前缀和思路;
这样遍历过去就完成了一次轰炸。
但是,这样是不现实的,因为不可能每次都这样做。但是下面一下就可以。
这里,我尽量写清楚这道好题的主要思路。
也就是使用a, b,c,d4个数组来存储1和-1;然后再箭头方向更新!就很好了。
#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
const int maxn = 3e3 + , L = 1e3;
const int maxm = 1e5 + ;
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 / ][y]++; b[x - l / ][y + ]--;
a[x + ][y - l / - ]--; b[x + ][y + l / + ]++;
}
void down(int x, int y, int l){
c[x + ][y - l / + ]++; d[x + ][y + l / ]--;
c[x + l / + ][y + ]--; d[x + l / + ][y]++;
} int main(){
scanf("%d%d%d", &n, &m, &k);
for (int i = , 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 == )down(x, y, l);
}
int res = ;
for (int i = ; i < n + * L; ++i)
{
int ans = ;
for (int j = ; j < m + * L; ++j){
ans += a[i][j] + b[i][j] + c[i][j] + d[i][j];
if (i >= L + && i <= L + n&&j >= L + && j <= L + m)res ^= ans;
a[i + ][j - ] += a[i][j];
b[i + ][j + ] += b[i][j];
c[i + ][j + ] += c[i][j];
d[i + ][j - ] += d[i][j];
}
}
cout << res << endl;
}