P1884

mywwzh · 2024-06-26 11:37:32 · 题解

要统计覆盖，而且不计重复，可以自然地想到差分后求前缀和的做法，并且此题数据范围较大，还需离散化。

我们定义结构体 Node 来存储每个矩形的左上角和右下角，f_{i,j} 表示横坐标 i 和纵坐标 j 处有多少个矩形覆盖。

对于每次覆盖，我们只需对 f 数组进行差分，最后前缀和还原出每个位置的实际覆盖次数。最后我们只需遍历每一个 f_{i,j}，如果其覆盖次数不为 0，就计算该位置所对应的面积并加到最终答案中即可。

#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
#define debug(a) cout << a << "\n";
#define pb push_back
#define mp make_pair
#define mem(a, b) memset(a, b, sizeof(a))
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
constexpr int MOD = 1e9 + 7;
constexpr int MAXN = 1e3 + 10;

struct Node
{
    int X1, Y1, X2, Y2; // X1, Y1 是左上角，X2, Y2 是右下角
};

Node a[4 * MAXN];
int b[4 * MAXN], c[4 * MAXN], f[4 * MAXN][4 * MAXN];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, top = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].X1 >> a[i].Y1 >> a[i].X2 >> a[i].Y2;
        // 将点扔进 b 数组，方便离散化
        b[++top] = a[i].X1;
        b[++top] = a[i].Y1;
        b[++top] = a[i].X2;
        b[++top] = a[i].Y2; 
    }
    sort(b + 1, b + top + 1);
    b[0] = INT_MIN;
    auto end = unique(b + 1, b + top + 1);
    int new_top = distance(b, end) - 1;
    for (int i = 1; i <= n; i++)
    {
        // 二分法离散化
        a[i].X1 = lower_bound(b + 1, end, a[i].X1) - b;
        a[i].Y1 = lower_bound(b + 1, end, a[i].Y1) - b;
        a[i].X2 = lower_bound(b + 1, end, a[i].X2) - b;
        a[i].Y2 = lower_bound(b + 1, end, a[i].Y2) - b; 
    }
    for (int i = 1; i <= new_top; i++)
    {
        c[i] = b[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = a[i].X1; j < a[i].X2; j++)
        {
            // 差分
            f[j][a[i].Y1]++; 
            f[j][a[i].Y2]--;
        }
    }
    for (int i = 1; i < new_top; i++)
    {
        for (int j = 1; j < new_top; j++)
        {
            f[i][j] += f[i][j - 1];
        }
    }
    ll ans = 0;
    for (int i = 1; i < new_top; i++)
    {
        for (int j = 1; j < new_top; j++)
        {
            if (f[i][j] != 0)
            {
                ans += (ll)(c[i + 1] - c[i]) * (c[j + 1] - c[j]); // 如果被覆盖过，计算面积
            }
        }
    }
    cout << ans;
    return 0;
}