链接：https://ac.nowcoder.com/acm/contest/317/E来源：牛客网
题目描述
小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
输入
4 5 4
1 2 2 1
1 3 3 5
1 3 2 3
2 2 4 3
输出
2题意：每次对一个菱形区域轰炸，求每个点被轰炸次数的异或和。题解：如果是矩形，很容易利用差分+二维前缀和解决(差分主要用于区间修改问题，前缀和主要用于单点查询问题)，但是由于是矩形，单点查询并不能通过简单的加减进行维护，于是动态差分诞生了，由于单点查询是按照行列顺序进行的，所以可以让差分数组不断地向下向右转移，具体见下图
1 #include<iostream>
2 #include<
string>
3 #include<algorithm>
4 #include<cstdio>
5 #include<vector>
6 #include<cstring>
7 using namespace std;
8 typedef
long long ll;
9 int a[
3019][
3019],b[
3019][
3019],c[
3019][
3019],d[
3019][
3019];
10 void up(
int x,
int y,
int l){
11 a[x-(l/
2)][y]++;b[x-(l/
2)][y+
1]--
;
12 a[x+
1][y-(l/
2)-
1]--;b[x+
1][y+(l/
2)+
2]++
;
13 }
14 void down(
int x,
int y,
int l){
15 c[x+
1][y-(l/
2)+
1]++;d[x+
1][y+(l/
2)]--
;
16 c[x+
1+(l/
2)][y+
1]--;d[x+(l/
2)+
1][y]++
;
17 }
18 int main(){
19 int n,m,q;
20 scanf(
"%d%d%d",&n,&m,&
q);
21 while(q--
){
22 int opt,x,y,l;
23 scanf(
"%d%d%d%d",&opt,&x,&y,&
l);
24 up(x+
1000,y+
1000,l);
25 if(opt==
1)down(x+
1000,y+
1000,l);
26 }
27 int ans0=
0;
28 for(
int i=
0;i<=n+
1000;i++
){
29 int ans=
0;
30 for(
int j=
0;j<=
3000;j++
){
31 ans+=a[i][j]+b[i][j]+c[i][j]+
d[i][j];
32 if(i>
1000&&j>
1000&&j<=
1000+
m){
33 ans0^=
ans;
34 }
35 if(i+
1<
3019&&j-
1>=
0){
36 a[i+
1][j-
1]+=
a[i][j];
37 d[i+
1][j-
1]+=
d[i][j];
38 }
39 if(i+
1<
3019&&j+
1<
3019){
40 b[i+
1][j+
1]+=
b[i][j];
41 c[i+
1][j+
1]+=
c[i][j];
42 }
43 }
44 }
45 cout<<ans0<<
endl;
46 return 0;
47 }
View Code
转载于:https://www.cnblogs.com/MekakuCityActor/p/10561113.html
