题解：P13787 地毯 加强版
zybgml_AFO
·
·
题解
题目链接：P13787 地毯 加强版
题目大意
给你一个有 n\times n 个格子的坐标，再在上面铺 m 块地毯，问你每个位置的行数加列数异或被多少个地毯覆盖的和。
做法1：暴力
我们利用一个二维数组来记录每个点被多少个地毯覆盖，最后按要求输出。可是那样的话，时间复杂度度太高了，有没有更简单且高效的方法呢？
有的兄弟，有的。想修改区间值的话 二维差分 是一个十分简单的方法。
正解：二维前缀和 + 二维差分
相关知识：一维前缀和 + 一维差分
一维前缀和
假如给你一个数组，你有没有一种可以用 O(1) 的时间复杂度求出其中的任意一个区间和的方法呢？一维前缀和 是一种可以只用时间复杂度为 O(n) 预处理就可以用 O(1) 的时间复杂度求出任意区间和的方法。它的原理简单易懂：
我们将数组中第 i 个数变成前 i 个数的总和，这样就完成预处理啦！
所以现在如何求区间和呢？假如有 5 个数：
1 2 3 4 5
预处理后 5 个数为：
1 3 6 10 15
而如果我们要求区间 [2,4] 的总和，只需要用预处理后的第 4 个数减去第 1 个数就可以了！
为什么呢？其实原理非常简单：预处理后的第 4 个数为前 4 个数的总和，第 1 个数为前 1 个数的总和。两者相减，不就是第 2 个数至第 4 个数的总和吗？
可是如果我们还要先更改区间值又该如何呢？
一维差分 可以帮你解决此问题：
一维差分
同样 5 个数：
1 2 3 4 5
我们要将区间 [2,4] 中的每一个数都加上 1 该如何做呢？
一维差分 同样需要先用时间复杂度为 O(n) 的预处理，使原数组的第 i 个数为前 i 个数的总和：
预处理后 5 个数为：
1 1 1 1 1
也就是说，本来的数组为现在预处理后的数组的前缀和数组！
现在，如果我们将第 2 个数加上 1 的话，本来的数组会有什么变化呢？
1 3 4 5 6
不难发现，从第 2 个数开始，每个数都加了 1。
聪明的人已经看出，现在我们只要将第 5 个数加上 -1，就完成了将区间 [2,4] 中的每一个数都加上 1 的操作。
原因是我们通过反向利用 一维前缀和 ，来高效修改了区间值。
二维前缀和
懂了 一维前缀和 的相信很快也能理解 二维前缀和。
二维前缀和 其实也很好推，这里不举例了。
假如有一个二维数组，我们要求 (1,1) 至 (x,y) 的矩阵中的所有数的和。
现在设 a[i][j] 为第 i 行第 j 列的数，s[i][j] 为 (1,1) 至 (i,j) 的矩阵中的所有数的和,那么：
利用容斥原理可以理解上式。
### 二维差分
**二维差分** 其实也同 **一维差分**一样，是“反向前缀和”。
同样 **一维差分**一样需要先用时间复杂度为 $O(n^2)$ 的预处理。设预处理后的数组为 $c$。
如果我们要将一个二维数组的 $(x,y)$ 至 $(z,s)$ 矩阵中的每一个数加 $1$ 只需 $4$ 步：
```cpp
c[x][y]++;
c[x][s+1]--;
c[z+1][y]--;
c[z+1][s+1]++;
```
现在都知道该如何做了吧！
# 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T&x){
x=0;char c;int sign=1;
do{c=getchar_unlocked();if(c=='-') sign=-1;} while(!isdigit(c));
do{x=x*10+c-'0';c=getchar_unlocked();}while(isdigit(c));
x*=sign;
}
int n,m;
int c[5050][5050];
int x,y,z,s;
long long ans;
int main(){
read(n),read(m);
for(int i=1;i<=m;i++){
read(x),read(y),read(z),read(s);
c[x][y]++;
c[x][s+1]--;
c[z+1][y]--;
c[z+1][s+1]++;
//差分处理
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
c[i][j]=c[i-1][j]+c[i][j-1]-c[i-1][j-1]+c[i][j];//前缀和处理
ans+=(i+j)^c[i][j];//计算答案
}
}
cout<<ans;
return 0;
}
```
这道题跟[P3397 地毯](https://www.luogu.com.cn/problem/P3397) 题干完全一样，只是数据增强与输出不同。可以复习巩固关于 **前缀和** 与 **差分** 的基础知识，也值得一做。