【牛客 - 317E】小a的轰炸游戏（差分，前缀和）

题干：

小a正在玩一款即时战略游戏，现在他要用航空母舰对敌方阵地进行轰炸
地方阵地可以看做是n×mn×m的矩形
航空母舰总共会派出qq架飞机。
飞机有两种，第一种飞机会轰炸以(xi,yi)(xi,yi)为中心，对角线长为lili的正菱形(也就是两条对角线分别于xx轴 yy轴平行的正方形)，而第二种飞机只会轰炸正菱形的上半部分(包括第xixi行)
(具体看样例解释)
现在小a想知道所有格子被轰炸次数的异或和
注意：不保证被轰炸的格子一定在矩形范围内，若越界请忽略

输入描述:

第一行三个整数n,m,qn,m,q，分别表示矩阵的长/宽/询问次数
接下来qq行，每行四个整数opt,x,y,lopt,x,y,l，表示飞机类型，轰炸的坐标，以及对角线长度
保证ll为奇数！

输出描述:

一个整数，表示所有格子被轰炸次数的异或和

示例1

输入

复制

输出

复制

说明

每次的操作矩阵即操作后的矩阵的值如下

0 0 0 0 0

0 1 0 0 0
0 0 0 0 0
0 0 0 0 0

0 0 1 0 0
0 2 1 1 0
1 1 1 1 1
0 1 1 1 0

0 0 1 0 0
0 3 1 1 0
2 2 2 1 1
0 2 1 1 0

0 0 1 1 0
0 3 2 2 1
2 2 2 1 1
0 2 1 1 0
最后把所有元素异或后为2

备注:

1⩽n,m⩽10001⩽n,m⩽1000

1⩽q⩽5∗1051⩽q⩽5∗105

保证opt=1/2,1⩽x,y,l⩽max(N,M)opt=1/2,1⩽x,y,l⩽max(N,M)

读入文件过大，请使用较快的读入方式

解题报告：

这题考查的是对差分数组和前缀和的理解。四个数组分别记录朝着四个方向下放的个数最后求个前缀，就代表着这一行中从这个点开始作为起点的轰炸区域个数，四个数组分别向着四个方向下放最终得到的四个数组分别是前。可以找个边长为1的操作模拟一下，虽然看着别扭但是没啥问题。也就是：数组中是差分数组，最后查询是前缀和查询。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 3030,ADD = 1000;
int a[MAX][MAX],b[MAX][MAX],c[MAX][MAX],d[MAX][MAX];
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() {
	int n,m,q;
	cin>>n>>m>>q;
	for(int op,x,y,l,i = 1; i<=q; i++) {
		scanf("%d%d%d%d",&op,&x,&y,&l);
		x+=ADD,y+=ADD;
		if(op == 1) up(x,y,l),down(x,y,l);
		if(op == 2) up(x,y,l);
	}
	for(int i = 1; i<=n+ADD*2; i++) {
		for(int j = 1; j<=m+ADD*2; j++) {
			a[i][j] += a[i-1][j+1];
			b[i][j] += b[i-1][j-1];
			c[i][j] += c[i-1][j-1];
			d[i][j] += d[i-1][j+1]; 
		}
	}
	int ans = 0;
	for(int i = 1; i<=n+ADD*2; i++) {
		int tmp = 0;
		for(int j = 1; j<=m+ADD*2; j++) {
			tmp += a[i][j] + b[i][j] + c[i][j] + d[i][j];
			if(i>=ADD+1 && i<=ADD+n && j>=ADD+1 && j<=ADD+m) ans ^=tmp;
		}
	}	
	cout << ans <<endl;
	return 0 ;
}