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; }
因此这里的差分和差分模板略有不同，没有那些加一