题解：AT_abc434_d [ABC434D] Clouds

wcmz · 2025-12-02 17:11:10 · 题解

ABC434D 题解

思路：

有 n 块云，每块云都有自己的覆盖范围，拿去云 k ，请问有几个放个没有被覆盖。这个问题很容易想到二维前缀和和差分。首先我们思考一个问题，如果一个方格 x 只被一朵云 k 所覆盖，那么将云 k 拿去，这个格子便不被覆盖了，那么思路便出来了。我们现统计一个二维差分数组，接着用前缀和统计每个格子的覆盖次数。根据上面的思路，我们先统计原本就没有被覆盖的格子，再统计只被云 k 覆盖的格子个数，最后统计即可。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll h = 2000;
ll w = 2000;

int main(){
    ll n;
    cin >> n;

    vector<vector<ll>>cld (h+2,vector<ll>(w+2,0));
    vector<vector<ll>>pos (n,vector<ll>(4));
    for(int i=0;i<n;i++){
        for(int j=0;j<4;j++) cin >> pos[i][j];

        cld[pos[i][0]][pos[i][2]]++;
        cld[pos[i][0]][pos[i][3]+1]--;
        cld[pos[i][1] + 1][pos[i][2]]--;
        cld[pos[i][1] + 1][pos[i][3] + 1]++;
    }

    for(int i=0;i<=h;i++){
        for(int j=0;j<=w;j++) cld[i][j+1] += cld[i][j];
    }

    for(int j=0;j<=w;j++){
        for(int i=0;i<=h;i++) cld[i+1][j] += cld[i][j];
    }

    vector<vector<ll>>ans (h+2,vector<ll>(w+2,0));
    ll fr = 0;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(cld[i][j] == 0) fr++;
            if(cld[i][j] == 1) ans[i][j]++;
        }
    }

    for(int i=0;i<=h;i++){
        for(int j=0;j<=w;j++) ans[i][j+1] += ans[i][j];
    }

    for(int j=0;j<=w;j++){
        for(int i=0;i<=h;i++) ans[i+1][j] += ans[i][j];
    }

    for(int i=0;i<n;i++){
        int u = pos[i][0] - 1;
        int d = pos[i][1];
        int l = pos[i][2] - 1;
        int r = pos[i][3];

        ll sum = ans[d][r] + ans[u][l] - ans[u][r] - ans[d][l];
        sum += fr;
        cout << sum << endl;
    }
}