P8648 油漆面积

· · 题解

P8648 油漆面积

upd：被 hack 了，应将数组开大点，感谢 @rui_er 的指出。

扫描线的板子题，不会的可以先写一下这道题。

题意简述

给定 n 个矩形，求这些矩形所覆盖的面积之和。

扫描线

扫描线顾名思义就是有一条线自底向上扫动（其实怎么扫都无所谓），通常用来求矩形所覆盖的面积或周长。

上面这张图很好的演示了扫描线的全过程，我们可以把整个矩形分成若干个小矩形，这些小矩形的高就是扫描线扫过的距离，而小矩形的长就可以用线段树来维护。

具体地，线段树的节点需要维护两个值，分别是 cnt 和 len，分别表示当前区间被覆盖的次数，区间内覆盖的长度和。

void update(int p) {
    if (t[p].cnt) t[p].len = a[t[p].r+1]-a[t[p].l];
    else t[p].len = t[p<<1].len+t[p<<1|1].len;
}

有了这段代码，剩下的就是线段树的板子了，于是就可以愉快的切过这道题了。

代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+5;
int n, tot, a[N<<2];
ll ans;//十年oi一场空，不开long long见祖宗
struct edge {
    int y, x1, x2, k;
} e[N<<1];
struct SegmentTree {
    int l, r;
    ll len, cnt;
} t[N<<3];
void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) return;
    int mid = (l+r)>>1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
}
void update(int p) {//向上传递
    if (t[p].cnt) t[p].len = a[t[p].r+1]-a[t[p].l];
    else t[p].len = t[p<<1].len+t[p<<1|1].len;
}
void change(int p, int l, int r, int x) {
    if (l <= t[p].l && t[p].r <= r) {
        t[p].cnt += x;
        update(p);
        return;
    }
    int mid = (t[p].l+t[p].r)>>1;
    if (l <= mid) change(p<<1, l, r, x);
    if (mid < r) change(p<<1|1, l, r, x);
    update(p);
}
bool cmp(edge x, edge y) {return x.y < y.y;}
int query(int x) {return lower_bound(a+1, a+tot+1, x)-a;}//查询
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        e[(i<<1)-1] = (edge){y1, x1, x2, 1};
        e[i<<1] = (edge){y2, x1, x2, -1};
        a[(i<<1)-1] = x1, a[i<<1] = x2;
    }
    n <<= 1;
    sort(e+1, e+n+1, cmp);
    sort(a+1, a+n+1);
    tot = unique(a+1, a+n+1)-a-1;//离散化
    build(1, 1, tot);
    for (int i = 1; i <= n; ++i) {
        change(1, query(e[i].x1), query(e[i].x2)-1, e[i].k);
        ans += t[1].len*(e[i+1].y-e[i].y);
    }
    cout << ans;
    return 0;
}

P8734，P1856，P1502，P5490 这些都是扫描线的题，有兴趣可以做一做。