题解 P1884 【[USACO12FEB]过度种植（银）Overplanting …】

· · 题解

扫描线板子题，可以去搜博客看一下。这里搬运一下以前口胡的。

首先将y坐标离散化，但是要保留原坐标。

我们用一根竖直的线从左向右依次扫描，每当与矩形的竖直边重合时就累加一次面积，相当于把并集图形分割为一个一个小的矩形。

具体来说，建立数组d[i]保存这个y坐标被覆盖了多少次，并把矩形的竖边按(x,y1,y2,d)表示，d表示这是矩形的左边界(1)还是右边界(-1)，比如图中第一条边就是(2,3,7,1)，并按x排序依次考虑。

对所有竖线先按x排序，有些写法里对竖线排序时如果x相等会按c排序，但是容易发现这是毫无影响的。

对于每条边，我们把[y1,y2)的值都加上d，表示这条左数边把y轴这些地方又覆盖了一次，或者右数边表示该矩形对y轴影响已经结束。

（为什么是左闭右开：我们把点转化为线段来求覆盖次数，点的数量是比线段的数量多1个的，比如第一条线段里[3,7]是有5个点的，但是放在d数组里只有4个值需要修改。）

接着统计答案，下一个矩形的宽就是相邻两根竖边的x坐标差，而长度就是d数组里至少被覆盖一次的坐标数。

（图中：2*4+2*6+1*8+2*7+1*7+1*4+3*4+0*0\ =\ 60）

d数组涉及了区间修改和区间查询，可以使用线段树来维护。

由于只需要查询(1,N)里的覆盖次数，我们的懒标记可以不用下推。更新时，如果一个节点有懒标记（表示自己被完全覆盖的次数），那么他的贡献就是区间总长度（因为被覆盖），否则递归计算左右儿子并相加。

#include <bits/stdc++.h>
#define MAX (2000 + 7)
using namespace std;

struct Node { int x, y0, y1, c; } a[MAX];
int cmp(Node a, Node b) { return a.x < b.x; }

unordered_map <int, int> H;

int N, M, qy[MAX];
long long ans;

struct Segtree
{
    #define i0 (i << 1)
    #define i1 (i << 1 | 1)
    int L[MAX << 2], R[MAX << 2], v[MAX << 2], len[MAX << 2];
    void init(int i, int l, int r)
    {
        L[i] = l, R[i] = r, v[i] = len[i] = 0;
        if (l != r) {
            int mid = l + r >> 1;
            init(i0, l, mid), init(i1, mid+1, r);
        }
    }
    void add(int i, int l, int r, int c)
    {
        if (r < L[i] || R[i] < l) return;
        if (l <= L[i] && R[i] <= r)
            v[i] += c;
        else add(i0, l, r, c), add(i1, l, r, c);
        if (v[i]) len[i] = qy[R[i]+1] - qy[L[i]];//完全覆盖时的长度应该是离散化前的y坐标（实际长度）。
        else len[i] = len[i0] + len[i1];
    }
} Seg;

int main()
{
    scanf("%d", &N), H.clear();
    for (int i = 1, x0, y0, x1, y1; i <= N; i++)
    {
        scanf("%d%d%d%d", &x0, &y1, &x1, &y0);//注意是左上和右下
        a[i] = Node{x0, y0, y1, 1};
        a[i+N] = Node{x1, y0, y1, -1};
        qy[++M] = y0, qy[++M] = y1;
    }
    sort(qy+1, qy + M+1), M = unique(qy+1, qy + M+1) - qy - 1;
    for (int i = 1; i <= M; i++)
        H[qy[i]] = i;//离散化

    Seg.init(1, 1, (N <<= 1));
    sort(a + 1, a + N + 1, cmp);
    for (int i = 1; i <= N; i++)
    {
        Seg.add(1, H[a[i].y0], H[a[i].y1] - 1, a[i].c);
        ans += (long long)Seg.len[1] * (a[i+1].x - a[i].x);
    } printf("%lld\n", ans);
}

另外，本题N规模为1000，最多2000个不同的坐标，线段树开8000是足够的，但是上面的代码如果开了O2就会WA。必须要开更大的空间才能过，如果有知道原因的dalao欢迎来踩。