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

Indestructible · 2025-08-15 11:39:38 · 题解

前言

题目传送门。在专栏阅读体验更佳。

洛谷 SCP-S1 2025 完善程序 2 居然考扫描线，错 3 道的我赶紧来恶补一下。

OI Wiki 上也有对扫描线算法的讲解，我就是通过这个自学的。

前置知识：线段树、离散化。

扫描线算法，顾名思义就是用一条线进行扫描的算法。

算法介绍

本题要求用扫描线算法求解 n 个各边与横坐标或纵坐标相平行的长方形的面积并。可以用下图形象化地观察（图片取自 OI Wiki）：

如图所示，我们用一根直线从下至上（也可以其他方向，这里默认从下至上）扫描所有长方形的长，得到新的一系列互不重叠的长方形，此时将各个长方形的面积相加即可。每个长方形的长是直线在组合图形内部的部分，宽是直线扫描过的长度。理解很容易，但要怎么去实现呢？

由于扫描的是线段而不是长方形，可以直接存储线段，然后按照纵轴高度排序。当一个长方形下端的长被扫描到后，被扫描的部分增加，而长方形上端的长被扫描到则减少，我们可以用一个变量存储 1 或 -1 来标识是长方形哪一端的长。具体地，对于一条线段，如果我们用 x_1, x_2 表示线段横轴的两个端点，y 表示线段纵轴高度，opt=1 \operatorname{or} -1，可以用如下的代码实现：

#define fr(i, x, y) for (int i = (x); i <= (y); i ++)
struct Segment{ 
    int x1, x2; // 线段起止点 
    int y;      // 线段高度 
    int opt;    // 权值 (+1/-1) 
}seg[N << 1];

bool cmp(Segment x, Segment y){
    // 按照纵轴高度 y 排序，特别地，如果 y 相等，则 opt = 1 优先 
    return x.y < y.y || (x.y == y.y && x.opt > y.opt);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    fr(i, 1, n){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        seg[i] = {x1, x2, y1, 1}, seg[i + n] = {x1, x2, y2, -1}; // 存边 
    }
    sort(seg + 1, seg + 1 + n * 2, cmp);
}

于是，我们就完成了线段的存储。

核心部分：面积并如何计算？

我们可以注意到，所有线段 x 轴的数将长分成了至多 2n 个部分，所以我们将这些数排序，存在数组 x 里。设定一个记录直线上线段的数组 cnt，则以数组 x 相邻两项的区间作下标，每次扫描将对应区间加上 opt。上面的动图中，cnt 数组就是该区间对应的下标存储的数（写法不唯一，这里只介绍这一种写法）。

因为 n\le 10^5，所以需要用到线段树；因为 x_1,x_2,y_1,y_2 \le 10^9，所以数组 x 需要离散化。

每次扫描，最终答案加上线段树中非零结点对应实际长度乘以和前一条线段的高度差即可。

由于离散化难以理解，因此贴出离散化代码。感谢 @Yamchip 大佬帮我找出 lower_bound 中的错误（就因为这个 18pts 了十发，应该不会有人和我一样吧）。

#define fr(i, x, y) for (int i = (x); i <= (y); i ++)
const int N = 1e5 + 22;
int n, m;
int x[N << 1]; // 离散化数组，线段数要乘 2

int f(int i){ // 对于离散化后的 i，查找实际值 
    return lower_bound(x + 1, x + 1 + m, i) - x;
    // 注意：新长度为 m，查找时需要正确设置！！ 
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    fr(i, 1, n){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x[i] = x1, x[i + n] = x2; // 将线段起止点加入离散化数组 
    }
    sort(x + 1, x + 1 + n * 2);
    m = unique(x + 1, x + 1 + n * 2) - x - 1; // 离散化，去重后长度为 m
}

线段树的实现细节

当你闷头打出线段树模板结果发现过不了时，你可能需要注意：

• 不用打懒标记。这里的线段树只需要存一个节点是否有值即可，不需要查询。
• 记得计算线段树中非零节点对应的实际长度。不要算成离散化后的长度，或使用错误方法计算。
• 存储区间，谨慎操作。单个区间 i 的长度为 x_{i + 1} - x_i，区间 i 至区间 j 的总和为 x_{j + 1} - x_i(i\le j)。对于每次修改，需要将 r 减 1 以计算正确区间，还有其他细节方面的处理。
• 线段个数是长方形的 2 倍，线段树本身需要 4 倍空间，因此至少要开 8 倍空间。一般为防止在叶子节点继续向下访问导致的问题，保险起见开 16 倍空间。
• 开 long long。

这里是线段树的实现：

#define fr(i, x, y) for (int i = (x); i <= (y); i ++)
#define int long long // 开 long long 
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1) // 线段树查找子节点

int ans;
int tr[N << 4];  // 线段树 (防意外开 16 倍) 
int len[N << 4]; // 标记的区间长度总和 (未离散化时) 
// 单个区间 i 的长度为 x[i + 1] - x[i]
// 注意，不用查询，无需懒标记 

void pushup(int pl, int pr, int p){ // 更新 len[] 值并向上传递 
    if (tr[p]) len[p] = x[pr + 1] - x[pl]; // 这部分在直线上 
    else if (pl == pr) len[p] = 0; // 这部分不在直线上，并且是叶子节点，特判 
    else len[p] = len[ls(p)] + len[rs(p)]; // 更新为子树上的值之和 
}

void update(int pl, int pr, int p, int l, int r, int k){
    // 线段树的修改操作 
    if (l <= pl && pr <= r){ // 查询到目标区间 
        tr[p] += k, pushup(pl, pr, p);
        return;
    }
    int mid = pl + pr >> 1;
    if (l <= mid) update(pl, mid, ls(p), l, r, k);
    if (r > mid) update(mid + 1, pr, rs(p), l, r, k);
    pushup(pl, pr, p);
}

signed main(){
    update(1, m - 1, 1, f(seg[1].x1), f(seg[1].x2) - 1, seg[1].opt);
        // 更新首条边，线段树按区间存储所以 m - 1、f(seg[1].x2) - 1 
    fr(i, 2, n << 1){
        ans += (seg[i].y - seg[i - 1].y) * len[1];
        update(1, m - 1, 1, f(seg[i].x1), f(seg[i].x2) - 1, seg[i].opt);
    }
    cout << ans << "\n";
}

时间复杂度证明

结论：扫描线算法的时间复杂度为 O(n\log n)。

证明：根据算法介绍及代码实现，在算法中，先以 O(2n \log 2n) 的时间复杂度离散化（sort、unique），然后对 2n 个线段（离散化去重后线段树总长为 m，但假设没有重复，则 m=2n）分别进行线段树上的操作，单次操作时间复杂度为 O(\log 2n)。代码中 f() 函数的 lower_bound 虽然也是 O(\log 2n)，但因为未和线段树维护结合，仅增加常数。因此，忽略常数后，最终的总时间复杂度为 O(n\log n)。

另外易知，忽略常数，空间复杂度为 O(n)。

最终实现

自认为写的还是比较易懂的，具体实现请看代码。

#include <bits/stdc++.h>
#define fr(i, x, y) for (int i = (x); i <= (y); i ++)
#define int long long // 开 long long 
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1) // 线段树查找子节点 
using namespace std;

const int N = 1e5 + 22;
int n, ans, m;
int x[N << 1]; // 离散化数组，线段数要乘 2 
struct Segment{ 
    int x1, x2; // 线段起止点 
    int y;      // 线段高度 
    int opt;    // 权值 (+1/-1) 
}seg[N << 1];
int tr[N << 4];  // 线段树 (防意外开 16 倍) 
int len[N << 4]; // 标记的区间长度总和 (未离散化时) 
// 单个区间 i 的长度为 x[i + 1] - x[i]
// 注意，不用查询，无需懒标记 

int f(int i){ // 对于离散化后的 i，查找实际值 
    return lower_bound(x + 1, x + 1 + m, i) - x;
    // 注意：新长度为 m，查找时需要正确设置！！ 
}

bool cmp(Segment x, Segment y){
    // 按照纵轴高度 y 排序，特别地，如果 y 相等，则 opt = 1 优先 
    return x.y < y.y || (x.y == y.y && x.opt > y.opt);
}

void pushup(int pl, int pr, int p){ // 更新 len[] 值并向上传递 
    if (tr[p]) len[p] = x[pr + 1] - x[pl]; // 这部分在直线上 
    else if (pl == pr) len[p] = 0; // 这部分不在直线上，并且是叶子节点，特判 
    else len[p] = len[ls(p)] + len[rs(p)]; // 更新为子树上的值之和 
}

void update(int pl, int pr, int p, int l, int r, int k){
    // 线段树的修改操作 
    if (l <= pl && pr <= r){ // 查询到目标区间 
        tr[p] += k, pushup(pl, pr, p);
        return;
    }
    int mid = pl + pr >> 1;
    if (l <= mid) update(pl, mid, ls(p), l, r, k);
    if (r > mid) update(mid + 1, pr, rs(p), l, r, k);
    pushup(pl, pr, p);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    fr(i, 1, n){
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        seg[i] = {x1, x2, y1, 1}, seg[i + n] = {x1, x2, y2, -1}; // 存边 
        x[i] = x1, x[i + n] = x2; // 将线段起止点加入离散化数组 
    }
    sort(x + 1, x + 1 + n * 2);
    m = unique(x + 1, x + 1 + n * 2) - x - 1; // 离散化，去重后长度为 m
    sort(seg + 1, seg + 1 + n * 2, cmp);
    update(1, m - 1, 1, f(seg[1].x1), f(seg[1].x2) - 1, seg[1].opt);
        // 更新首条边，线段树按区间存储所以 m - 1、f(seg[1].x2) - 1 
    fr(i, 2, n << 1){
        ans += (seg[i].y - seg[i - 1].y) * len[1];
        update(1, m - 1, 1, f(seg[i].x1), f(seg[i].x2) - 1, seg[i].opt);
    }
    cout << ans << "\n";
    return 0; // 好习惯让 CSP 2025 RP++
}

AC 记录。

写在最后

扫描线算法除了求矩形面积并，还可以求矩形周长并，比如 P1856 [IOI 1998 / USACO5.5] 矩形周长 Picture。这里就不讲了，因为我还没做。

希望这篇题解对大家的代码实现有些帮助，但是我认为，对于初学者还没那么简单易懂，以后会尽量改进，谢谢！