题解：AT_abc434_d [ABC434D] Clouds

ryf2011 · 2025-11-30 08:06:07 · 题解

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 地毯加强版。

:::info[二维差分代码]

//差分数组为 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.这里“谁”覆盖

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

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

:::info[前缀和代码]

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 就直接计算，将无法判断一个位置的结果是累加的还是单独的，无法统计。

:::info[改进代码]{open}

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.完整代码

注：代码仅供参考。

#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;
}