P8648 [蓝桥杯 2017 省 A] 油漆面积

1.首先想到的错解

看到数据范围，就想先写个n^2的暴力：先把所有矩形的面积都算出来，然后再把所有重合的部分挨个减去，把每个重合的部分当成一个个小矩形，用set来判重。

画一个稍复杂些的样例，就会发现，在这些由重合部分产生的小矩形之间，仍有重合，所以这种算法，会导致算出来的重合部分偏大，而导致最后的答案偏小。

2.正解

扫描线，但是暂时不会。

3.因为这道题的n小于等于10000，所有的坐标也都小于等于10000，所以可以直接用差分和前缀和来做，时间复杂度为n^2（这里面还有个小技巧，开10^8的数组可能太大了，但是注意到，最后的答案不会超过10^4，因此可以不开int，开short来省空间）

同时注意到，全局变量下y1会有冲突，但是局部变量不会。

同时还要注意：是对角点的坐标，不是格子的坐标

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#define For(i, j, n) for (int i = j; i <= n; ++i)
using namespace std;

const int N = 10005;

short n;

inline short read()
{
    short x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9')
        ch = getchar();
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}

short a[N][N];

short mx, my;

void insert(short x1, short y1, short x2, short y2)
{
    /*a[x1][y1]++;
    a[x1][y2 + 1]--;
    a[x2 + 1][y1]--;
    a[x2 + 1][y2 + 1]++;*/
    ++a[x1][y1];
    --a[x1][y2];
    --a[x2][y1];
    ++a[x2][y2];
}

int main()
{
    n = read();
    for (short i = 1; i <= n; i++)
    {
        short x1 = read() + 1, y1 = read() + 1, x2 = read() + 1, y2 = read() + 1;
        mx = max(mx, x2);
        my = max(my, y2);
        insert(x1, y1, x2, y2); // 矩阵差分
    }
    int ans = 0;
    for (short i = 1; i <= mx; i++)
        for (short j = 1; j <= my; j++)
        {
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
            if (a[i][j] >= 1)
                ans++; // 以每个格子为单元来进行答案的统计
        }
    printf("%d\n", ans);
    return 0;
}

因此这里的差分和差分模板略有不同，没有那些加一