题解：AT_abc434_d [ABC434D] Clouds

BNCDBD · 2025-12-01 21:20:47 · 题解

差分 + 前缀和。

对于每个矩形，只有在它内部只被覆盖一次的格子，删除这个矩形之后会受影响。

所以，我们只需要在输入矩形的时候用差分把矩形内部的格子的覆盖次数加一。之后再前缀和两次：一次统计覆盖次数，一次统计只被覆盖一次的格子数量。

输出时，把原本就没有被覆盖的格子数量加上这个矩形内部只被覆盖一次的格子数量即为答案。

Code

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define eb emplace_back
#define mkp(x,y) make_pair((x),(y))
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define fir first
#define sec second
#define il inline
#define re register
#define rep(x,st,en) for(int x=st;x<=en;++x)
#define down(x,st,en) for(int x=st;x>=en;--x)
//#define mp(x,y) make_pair((x),(y))
//#define int long long
using namespace std;
struct rect{
    int x,y,xx,yy;
}a[200005];
int n;
ll g[2005][2005];
ll s[2005][2005];
signed main(){
    scanf("%d",&n);
    rep(i,1,n){
        scanf("%d%d%d%d",&a[i].x,&a[i].xx,&a[i].y,&a[i].yy);
        ++g[a[i].x][a[i].y];--g[a[i].x][a[i].yy+1];--g[a[i].xx+1][a[i].y];++g[a[i].xx+1][a[i].yy+1];//覆盖次数+1 
    }
    ll ans=0;
    rep(i,1,2000){
        rep(j,1,2000){
            g[i][j]+=g[i-1][j]+g[i][j-1]-g[i-1][j-1];
            if(g[i][j]==0)++ans;//本来就没覆盖过的格子 
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+(g[i][j]==1);//统计只覆盖一次的格子的数量 
        }
    }
    rep(i,1,n){
        ll sum=s[a[i].xx][a[i].yy]-s[a[i].x-1][a[i].yy]-s[a[i].xx][a[i].y-1]+s[a[i].x-1][a[i].y-1];//矩形内部只被覆盖一次的格子的数量 
        printf("%lld\n",ans+sum);//加上原本的数量并输出 
    }
    return 0;
}

AC Submission