0.前言

这是一个神奇又普通的做法，你并不知道作者的脑回路是怎样的。

本题解无 AI 生成。

1.题目思路

由于网格大小是

2000 \times 2000

的，我们很容易想到暴力遍历网格。但

N

的大小过大，于是我们考虑一种先打标记的方法来记录覆盖次数，那就是二维差分。

1-1.这里“被”覆盖

对于输入的覆盖范围，我们直接使用二维差分标记，但是，如何将输入的数据对应坐标呢？

假设我们当前依次输入了

U_i,D_i,L_i,R_i

四个数表示第

i

个范围，设范围左上角的坐标是

(x_1,y_1)

，右下角是

(x_2,y_2)

，则

U_i,D_i,L_i,R_i

分别对应

x_1,y_1,x_2,y_2

。

举例：当输入 1 3 4 6 时，范围的左上角坐标为

(1,4)

，右下角坐标为

(3,6)

。

这样，我们就转化成了二维差分问题。

1-2.二维差分

确定覆盖范围的左上角和右下角坐标后，我们可以直接套用二维差分。

如果你没有学过差分，请移步至 P2367 语文成绩。

如果你没有学过二维差分，请移步至 P13787 地毯加强版。

二维差分代码

CPP

12345//差分数组为 d，xa,ya,xb,yb 分别表示 x_1,y_1,x_2,y_2
d[xa][ya]++;
d[xb+1][yb+1]++;
d[xa][yb+1]--;
d[xb+1][ya]--;

1-3.这里“谁”覆盖

我们注意到一个关键性质：每一次的答案仅与只覆盖一次的位置有关，因为覆盖多次的位置即使去掉一片云仍然还会被覆盖。

差分后，我们可以直接用前缀和还原出网格中每个点的覆盖次数。

前缀和代码

CPP

d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1]; //自己加上左边，再加上上边，最后减去重合的。

然后，怎样确定覆盖一次的位置到底是哪片云覆盖的呢？

此时，由于作者个人脑抽，我们要对差分数组进行一次“大改造”。

我们已经知道

N \le 2 \times 10^5

，所以

N

最大为

2 \times 10^5

，如果给云从

1

开始编号，则不会有云的编号大于

2 \times 10^5

。

这时候，一个神奇的做法诞生了：将差分数组由原本的加、减

1

，变成加、减

2 \times 10^5 + i

。这是什么意思？

也就是说，此时的差分数组不再表示覆盖次数，而是表示覆盖编号的和，因为我们并不关心被覆盖大于一次的位置。换句话说，此时还原后覆盖一次的位置的数据都在

2 \times 10^5 + 1

至

2 \times 10^5 + N

之间，而且更妙的是，此时我们可以

O(1)

计算覆盖位置云的编号了，即直接减去

2 \times 10^5

！

对于这种做法，如果不加

2 \times 10^5

就直接计算，将无法判断一个位置的结果是累加的还是单独的，无法统计。

改进代码

CPP

int now=max_m+i; //max_m=2e5
d[xa][ya]+=now;
d[xb+1][yb+1]+=now;
d[xa][yb+1]-=now;
d[xb+1][ya]-=now;

对于最初云覆盖的总面积，只需记录数据大于

0

的位置个数即可，第

i

个答案即为

2000^2

减去总面积再加上第

i

片云独占的面积。

2.完整代码

注：代码仅供参考。

CPP

12345678910111213141516171819202122232425262728293031323334#include<bits/stdc++.h>
using namespace std;
const int max_n=2002;
const int max_m=2e5; //最大数
int n,xa,ya,xb,yb;
int ans[max_m+5],cnt; //ans[] 记录答案，cnt 记录总面积
long long d[max_n][max_n]; //差分数组，记得开 long long！
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d %d %d",&xa,&xb,&ya,&yb);
		int now=max_m+i;
		d[xa][ya]+=now;
		d[xb+1][yb+1]+=now;
		d[xa][yb+1]-=now;
		d[xb+1][ya]-=now;
	}
	for(int i=1;i<=2000;i++){
		for(int j=1;j<=2000;j++){
			d[i][j]+=d[i-1][j]+d[i][j-1]-d[i-1][j-1];
			long long frnum=d[i][j]-max_m;
			if(frnum>=1&&frnum<=max_m){ //只被覆盖一次
				ans[frnum]++;
			}
			if(frnum>0){
				cnt++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d\n",2000*2000-cnt+ans[i]); //计算答案
	}
	return 0;
}

题解：AT_abc434_d [ABC434D] Clouds

文章操作