扫描线笔记

Garbage_fish · 2024-10-13 21:39:39 · 算法·理论

看名字很高级，实际上非常好理解的一个算法。

P5490 【模板】扫描线 & 矩形面积并

就是要求平面上若干个矩形，覆盖的面积的总和。

如上图所示，可以沿着红色的线（也就是每个矩形的上下边）将这个面积并分割成三部分。

从下往上看，先将 x_2\sim x_4 这一段区间增加 1（意义为新增 1 个图形覆盖这段区间），然后 (x_4-x_2)\times (l_2-l_1) 就是绿色的面积。
接着再看 l_2 和 l_3 之间，将 x_1\sim x_3 这一段区间增加 1，此时 x_1\sim x_2 有一个矩形覆盖，x_2\sim x_3 有两个矩形覆盖，x_3\sim x_4 有一个矩形覆盖。同理将 (x_4-x_1)\times (l_3-l_2) 得到蓝色的面积。
接着看 l_3 和 l_4 之间，到了右侧矩形的上边了，将 x_2\sim x_4 这一段区间减 1，此时 x_1\sim x_3 有一个矩形覆盖，(x_3-x_1)\times (l_4-l_3) 得到的就是黄色的面积。
三部分面积相加就是答案。

从上面可以发现，这个算法就是一直在进行区间加和区间减。所以可以考虑用线段树。

将灰线的 x 数组从小到大排好序并去重，线段树的一个节点 (l,r) 可以代表维护线段 (x_l,x_r) 的信息。其中根节点维护的就是 (x_1,x_m)（假设去重之后 x 有 m 项）。每次更新的时候，维护每条线段的覆盖矩形个数，和对答案的贡献。

但是还有个问题，如果有两段区间分别是 (100,200)，(200,300)，更新 (100,200) 时会把第二个区间也给更新了，但显然第二个区间不需要更新（两个点覆盖在一起，又不是两个格子，怎么会影响答案呢），所以修改定义，线段树的一个节点 (l,r) 维护 (x_l,x_{r+1})，这样就可以把 update 函数中的 x_l>uR\vee x_r<uL 的退出条件改为 x_l\ge uR \vee x_r\le uL，就可以防止那种情况（手玩一下就会发现确实如此）。

记得线段树的定义改了，最大的区间是 (1,m-1)。

记得开 8 倍空间，要是不像代码注释那里特判一下叶子节点的情况，还要再多 2 倍开 16 倍空间。

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 10;
int n, a[N];
struct LINE {
    int l, r, h, val;
} line[N];
bool cmp(LINE x, LINE y) {
    return x.h < y.h;
}
namespace Segtree {
#define ls (rt << 1)
#define rs (rt << 1 | 1)
    struct TREE {
        int cnt, len;
    } tree[N];
    void push_up(int rt, int l, int r) {
        if (tree[rt].cnt)
            tree[rt].len = a[r + 1] - a[l];
        else if (l == r) // 叶子节点没被覆盖直接清零，不 push_up。
            tree[rt].len = 0;
        else
            tree[rt].len = tree[ls].len + tree[rs].len;
    }
    void update(int rt, int l, int r, int x, int y, int v) {
        if (a[l] >= y or a[r + 1] <= x)
            return;
        if (x <= a[l] and a[r + 1] <= y) {
            tree[rt].cnt += v;
            push_up(rt, l, r);
            return;
        }
        int mid = l + r >> 1;
        update(ls, l, mid, x, y, v);
        update(rs, mid + 1, r, x, y, v);
        push_up(rt, l, r);
    }
}
using namespace Segtree;
signed main() {
    IOS;
    cin >> n;
    for (int i = 1, xa, ya, xb, yb; i <= n; i++) {
        cin >> xa >> ya >> xb >> yb;
        a[i] = xa, a[i + n] = xb;
        line[i] = {xa, xb, ya, 1};
        line[i + n] = {xa, xb, yb, -1};
    }
    n <<= 1;
    sort(line + 1, line + n + 1, cmp);
    sort(a + 1, a + n + 1);
    int m = unique(a + 1, a + n + 1) - (a + 1), ans = 0;
    for (int i = 1; i < n; i++) {
        update(1, 1, m - 1, line[i].l, line[i].r, line[i].val);
        ans += tree[1].len * (line[i + 1].h - line[i].h);
    }
    cout << ans;
    return 0;
}

扫描线 笔记

P5490 【模板】扫描线 & 矩形面积并

扫描线笔记