题解：AT_abc434_d [ABC434D] Clouds

Jayfeather2012 · 2025-12-01 11:00:53 · 题解

题目大意

有 n 朵长方形的云，每块云的编号为 i\ (1\le i\le n)，盖在一块 2000 \times 2000 的网格上，给定每块云的覆盖范围，求撤掉第 i 朵云时，有多少个网格是没有被覆盖的。

思路

容易发现：

• 当且仅当一个网格没有被云覆盖，无论撤掉那一朵云，它的状态都不会改变；
• 当且仅当一个网格只被一朵云覆盖时，撤掉这朵云之后，没有被覆盖的网格的数量会增加，于是，撤掉一朵云之后，没有被覆盖的网格的数量会增加仅被这朵云覆盖的网格数量；
• 当且仅当一个网格被两朵或两朵以上的云覆盖时，无论撤掉那一朵云，没有被覆盖的网格的数量都不会增加。

于是我们用一个差分维护每个网格覆盖云的数量，用另一个差分维护覆盖云数量 =1 的网格的编号。
设所有被数量 \ge2 的云覆盖的网格的数量为 sum，仅被第 i\ (1\le i\le n) 朵云覆盖的网格数量为 cnt_i，对差分数组做前缀和求出原数组，遍历数组，统计出 sum 及 cnt_i，则撤掉第 i 朵云时，有没有被云覆盖的网格数量为 2000\times2000-sum+cnt_i。

代码

#include<bits/stdc++.h>
#define ll long long
#define pp pair<int,int>
using namespace std;
const int N=2005,T=200005;
int n,t,sum,u[T],d[T],l[T],r[T],a[N][N],b[N][N],cnt[T];
//a数组维护每个方格覆盖云的编号，b数组维护每个方格覆盖云的数量。
//t相当于题目中的n。
void add1(int xa,int ya,int xb,int yb){
    ++b[xa][ya];--b[xa][yb+1];
    --b[xb+1][ya];++b[xb+1][yb+1];
}
//对每个方格覆盖云的数量做差分。
void add2(int xa,int ya,int xb,int yb,int k){
    a[xa][ya]+=k;a[xa][yb+1]-=k;
    a[xb+1][ya]-=k;a[xb+1][yb+1]+=k;
}
//对每个方格覆盖云的编号做差分。
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    n=2000;cin>>t;
    for(int i=1;i<=t;++i)cin>>u[i]>>d[i]>>l[i]>>r[i];
    for(int i=1;i<=t;++i){
        add1(u[i],l[i],d[i],r[i]);
        add2(u[i],l[i],d[i],r[i],i);
//调用差分函数。
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
//前缀和求出原数组。
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            if(b[i][j]>=1)++sum;
            if(b[i][j]==1)++cnt[a[i][j]];
//计算sum和cnt[i]。
        }
    }
    for(int i=1;i<=t;++i)cout<<n*n+cnt[i]-sum<<"\n";
    return 0;
}