题解：AT_abc434_d [ABC434D] Clouds
hyc1207
·
·
题解
题目大意
天空中有 2000\times2000 的方格，和 N(1\le N\le 2\times10^5) 朵云，所有满足 U_i\le r\le D_i 和 L_i\le c\le R_i 格子 (r,c) 被云朵 i 覆盖。输出
## 思路
首先考虑暴力做法，对于每朵云，将所覆盖方格上的云朵数量加 $1$，最终统计出每个方格上云朵的数量。接着枚举每个 $i$，将第 $i$ 朵云所覆盖的方格上的云朵数减 $1$，接着枚举每个方格，统计云朵数为 $0$ 的方格的数量。
```cpp
for (int i = 1; i <= n; i++)
{
int u,d,l,r;
cin >> u >> d >> l >> r;
m[i] = {u,d,l,r};
for (int j = u; j <= d; j++) for (int k = l; k <= r; k++) cnt[j][k]++;
}
for (int i = 1; i <= n; i++)
{
for (int j = m[i].u; j <= m[i].d; j++) for (int k = m[i].l; k <= m[i].r; k++) cnt[j][k]--;
int num = 0;
for (int j = 1; j <= 2000; j++) for (int k = 1; k <= 2000; k++) if (cnt[j][k] == 0) num++;
cout << num << endl;
for (int j = m[i].u; j <= m[i].d; j++) for (int k = m[i].l; k <= m[i].r; k++) cnt[j][k]++;
}
```
时间复杂度为 $O(NC)$，其中 $C$ 为方格数量，最大为 $2000\times2000$，显然会超时。
由于以上思路中存在许多统计数量的内容，可以使用差分前缀和进行优化：先用二维差分数组记录方格上云朵数量间的差值，接着通过前缀和得出每个方格上云朵的数量，将统计数量的时间复杂度降至 $O(N+C)$，接着枚举所有方格统计被云朵覆盖的方格数量 $num$。由于删除云朵后，只会影响到仅被该云朵覆盖的方格数，也就是被该云朵覆盖的方格中，被云朵覆盖数量为 $1$ 的方格数量。所以可以使用一个前缀和数组统计前面的方格中，被云朵覆盖数量为 $1$ 的方格数量，在枚举每朵云时，可在 $O(1)$ 的时间复杂度内求解出答案。此时将云朵 $i$ 删除后未被覆盖的云朵数量为 $2000\times2000-(num-k_i)$，$k_i$ 表示被云朵 $i$ 覆盖的方格中，被云朵覆盖数量为 $1$ 的方格数量。
### 二维差分前缀和
设二位数组 $a$ 的前缀和数组为 $pa$，则 $pa_{i,j}=\sum_{r=1}^i\sum_{c=1}^ja_{r,c}$。根据容斥原理，可以得到：$a_{i,j}=pa_{i,j}-pa_{i-1,j}-pa_{i,j-1}+pa_{i-1,j-1}$。根据以上式子，可以得出差分数组 $da_{i,j}$ 的值为 $a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}$。如果要将满足 $u\le x\le d$ 且 $l\le y\le r$ 的 $a_{x,y}$ 都增加 $1$，则根据求解 $da_{i,j}$ 的式子，可以发现只有 $da_{u,l}$ 和 $da_{d+1,r+1}$ 的值会加 $1$，$da_{u,r+1}$ 和 $da_{d+1,l}$ 的值会减 $1$，而其他值不变。
则在以上题目中需要使用到的式子有：
式子 A：$da_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}$。
式子 B：$a_{i,j}=da_{i,j}+a_{i-1,j}+a_{i,j-1}-a_{i-1,j-1}$。
式子 C：$pa_{i,j}=a_{i,j}+pa_{i-1,j}+pa_{i,j-1}-pa_{i-1,j-1}$。
式子 D：$a_{i,j}=pa_{i,j}-pa_{i-1,j}-pa_{i,j-1}+pa_{i-1,j-1}$。
式子 A,B 用于统计每个格子上云朵的数量，式子 C,D 用于统计相应格子内仅被 $1$ 朵云朵覆盖的格子的数量。
## AC Code
```cpp
#include <iostream>
using namespace std;
const int N = 2005;
struct Cloud
{
int u,d,l,r;
}c[200005];
int df[N][N]; //统计覆盖云朵数的差分数组
int cnt[N][N]; //覆盖云朵数
int pcnt1[N][N]; //统计仅被 1 朵云朵覆盖的方格数量的前缀和数组
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int u,d,l,r;
cin >> u >> d >> l >> r;
df[u][l]++; //套用式子 A
df[u][r+1]--;
df[d+1][l]--;
df[d+1][r+1]++;
c[i] = {u,d,l,r};
}
for (int i = 1; i <= 2000; i++) for (int j = 1; j <= 2000; j++) cnt[i][j] = df[i][j]+cnt[i-1][j]+cnt[i][j-1]-cnt[i-1][j-1]; //套用式子 B
int num = 0;
for (int i = 1; i <= 2000; i++) for (int j = 1; j <= 2000; j++) if (cnt[i][j] > 0) num++;
for (int i = 1; i <= 2000; i++) for (int j = 1; j <= 2000; j++) pcnt1[i][j] = pcnt1[i-1][j]+pcnt1[i][j-1]-pcnt1[i-1][j-1]+(cnt[i][j] == 1); //套用式子 C
for (int i = 1; i <= n; i++)
{
int k = pcnt1[c[i].d][c[i].r]-pcnt1[c[i].u-1][c[i].r]-pcnt1[c[i].d][c[i].l-1]+pcnt1[c[i].u-1][c[i].l-1]; //套用式子 D
cout << 2000*2000-num+k << endl;
}
return 0;
}
```