题解：AT_abc434_d [ABC434D] Clouds

null___ · 2025-12-01 22:40:27 · 题解

• 对于此类问题首先考虑二维差分，但常规的二维差分只能求出每个格子分别被几朵云覆盖。但对于本题需要求出只删除某朵云后，有多少格子没有被云朵覆盖。显然我们需要知道对于一个 i，有多少格子只被云朵 i 覆盖。此时便涉及到了一个经典技巧。
• 用数组 a[i][j] 来记录 (i,j) 被多少云朵覆盖，用数组 b[i][j] 记录所有覆盖了 (i,j) 的云朵的编号之和。我们分别维护两个数组的差分数组。
• 若 a[i][j]=0，那么 (i,j) 没有被任何云朵覆盖；若 a[i][j]=1，那么 (i,j) 被且仅被编号为 b[i][j] 的云朵覆盖。
• 用 cnt0 表示没有被任何云朵覆盖的格子数量，用 only[i] 表示仅被云朵 i 覆盖的格子的数量，删除云朵 i 后，没被任何云朵覆盖的格子数量便为 cnt0+only[i]。

int a[2005][2005],b[2005][2005],only[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int x1,y1,x2,y2;
        cin>>x1>>x2>>y1>>y2;
        a[x1][y1]++,a[x1][y2+1]--,a[x2+1][y1]--,a[x2+1][y2+1]++;
        b[x1][y1]+=i,b[x1][y2+1]-=i,b[x2+1][y1]-=i,b[x2+1][y2+1]+=i;
    }
    int cnt0=0;
    for(int i=1;i<=2000;i++){
        for(int j=1;j<=2000;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];
            if(!a[i][j])cnt0++;
            if(a[i][j]==1)only[b[i][j]]++;
        }
    }
    for(int i=1;i<=n;i++){
        cout<<cnt0+only[i]<<endl;
    }
}