小a的轰炸游戏（动态差分）

本文主要是介绍小a的轰炸游戏（动态差分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/problem/22146
来源：牛客网

小a的轰炸游戏
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld
题目描述
小a正在玩一款即时战略游戏，现在他要用航空母舰对敌方阵地进行轰炸
地方阵地可以看做是n \times mn×m的矩形
航空母舰总共会派出qq架飞机。
飞机有两种，第一种飞机会轰炸以(x_i, y_i)(x i ,y i )为中心，对角线长为l_il i
的正菱形(也就是两条对角线分别于xx轴 yy轴平行的正方形)，而第二种飞机只会轰炸正菱形的上半部分(包括第x_ix i 行)
(具体看样例解释)
现在小a想知道所有格子被轰炸次数的异或和
注意：不保证被轰炸的格子一定在矩形范围内，若越界请忽略
输入描述:
第一行三个整数n, m, qn,m,q，分别表示矩阵的长/宽/询问次数
接下来qq行，每行四个整数opt, x, y, lopt,x,y,l，表示飞机类型，轰炸的坐标，以及对角线长度
保证ll为奇数！
输出描述:
一个整数，表示所有格子被轰炸次数的异或和
示例1
输入
复制

输出
复制

在这里插入图片描述

思路：
很容易想到先这样差分：

这样差分之后还是满足不了时间复杂度。
仔细观察上面补全的图，
我们其实可以在这个基础上继续差分，
差分上再差分：
（黄色部分是红色部分的差分）

Ac_code:

#include <bits/stdc++.h>using namespace std;
const int N = 2500;
const int len = 510;//整体移动的距离，方便作差分的差分
int u1[N][N],u2[N][N];//记录上半部分差分的差分
int d1[N][N],d2[N][N];记录下半部分差分的差分
int n,m,q;
inline void read(int &x)
{char ch;int num = 0;while((ch=getchar())&&isdigit(ch))num = num*10 + (ch-'0');x = num;
}
inline void update(int op,int xi,int yi,int li)
{int t = li/2;u1[xi-t][yi]++;u1[xi+1][yi-t-1]--;u2[xi-t][yi+1]--;u2[xi+1][yi+t+2]++;if(op == 1){d1[xi+1][yi-t+1]++;d1[xi+t+1][yi+1]--;d2[xi+1][yi+t]--;d2[xi+t+1][yi]++;}
}
int main()
{read(n);read(m);read(q);//cout<<n<<" "<<m<<endl;int op,x,y,l;while(q--){read(op);read(x);read(y);read(l);update(op,x+len,y+len,l);}long long ans = 0;for(int i = 1; i < n+2*len; i++){int num = 0;for(int j = 1; j < m+2*len; j++){num += u1[i][j]+u2[i][j]+d1[i][j]+d2[i][j];if(i>len&&i<=len+n&&j>len&&j<=len+m){ans ^= num;//cout<<i<<" "<<j<<" :";//cout<<num<<endl;}//此时就可以动态更新差分了u1[i+1][j-1] += u1[i][j];u2[i+1][j+1] += u2[i][j];d1[i+1][j+1] += d1[i][j];d2[i+1][j-1] += d2[i][j];}}printf("%lld\n",ans);return 0;
}