洛谷题单指南-前缀和差分与离散化-P1884 [USACO12FEB] Overplanting S

原题链接：https://www.luogu.com.cn/problem/P1884

题意解读：给定n个矩形的平面直角坐标系下左上角、右下角的坐标，计算这n个矩形能覆盖的的格子数。

解题思路：

直观上来看，此题是一个差分应用，针对二维差分数组，将n个矩形区域内每个格子的值加1，然后统计有多少个不为0的格子即可。

但是！坐标值取值范围是−10^8≤x1​,y1​,x2​,y2​≤10^8，定义二维数组会爆内存，枚举时间也无法保证。因此，需要将坐标值进行离散化！

第一步：将所有坐标值读入，离散化处理

这里，介绍一个借助于map来离散化的方式，设c[]是所有坐标排序、去重后的数组，h是一个map<int,int>

将所有真实坐标数字映射到他的相对位置只需要：

for(int i = 1; i <= cnt; i++)
{
    h[c[i]] = i; //借助于map，保存原数字与离散化之后数字的关系
}

第二步：将离散化后的n个矩形区域进行差分数组+1

这里，要注意，对于二维差分数组子矩阵每个格子加上1，格子的坐标应该是(x1,y1-1)(x2,y2-1)

对应操作为：

 //在差分矩阵上对区间进行+1操作，注意求面积时(x2,y2)不包括
for(int i = 1; i <= n; i++)
{
    a[X1[i]][Y1[i]] += 1;
    a[X2[i]][Y1[i]] -= 1;
    a[X1[i]][Y2[i]] -= 1;
    a[X2[i]][Y2[i]] += 1;
}

第三步：计算还原的前缀和数组

for(int i = 1; i < cnt; i++)
    for(int j = 1; j < cnt; j++)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

第四步：根据前缀和数组不为0的格子，计算格子对应真实格子的数量

 //计算答案
for(int i = 1; i < cnt; i++)
    for(int j = 1; j < cnt; j++)
        if(s[i][j] > 0) ans += 1ll * (c[i + 1] - c[i]) * (c[j + 1] - c[j]);

100分代码：

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

const int N = 1005;

int X1[N], Y1[N], X2[N], Y2[N];
int c[4 * N], cnt;
map<int,int> h;
int a[4 * N][4 * N]; //差分矩阵
int s[4 * N][4 * N]; //二维前缀和
int n;
long long ans;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> Y1[i] >> X2[i] >> Y2[i] >> X1[i]; //输入时将平面直角坐标系转换为二维数组坐标
        c[++cnt] = X1[i];
        c[++cnt] = Y1[i];
        c[++cnt] = X2[i];
        c[++cnt] = Y2[i];
    }
    //排序、去重
    sort(c + 1, c + cnt + 1);
    int j = 0;
    for(int i = 1; i <= cnt; i++)
        if(i == 1 || c[i] != c[i - 1])
            c[++j] = c[i];
    cnt = j;
    //离散化
    for(int i = 1; i <= cnt; i++)
    {
        h[c[i]] = i; //借助于map，保存原数字与离散化之后数字的关系
    }
    for(int i = 1; i <= n; i++)
    {
        X1[i] = h[X1[i]];
        Y1[i] = h[Y1[i]];
        X2[i] = h[X2[i]];
        Y2[i] = h[Y2[i]];
    }
    //在差分矩阵上对区间进行+1操作，注意求面积时(x2,y2)不包括
    for(int i = 1; i <= n; i++)
    {
        a[X1[i]][Y1[i]] += 1;
        a[X2[i]][Y1[i]] -= 1;
        a[X1[i]][Y2[i]] -= 1;
        a[X2[i]][Y2[i]] += 1;
    }
    //还原前缀和
    for(int i = 1; i < cnt; i++)
        for(int j = 1; j < cnt; j++)
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    //计算答案
    for(int i = 1; i < cnt; i++)
        for(int j = 1; j < cnt; j++)
            if(s[i][j] > 0) ans += 1ll * (c[i + 1] - c[i]) * (c[j + 1] - c[j]);
    cout << ans;
    return 0;
}