高效扫描线算法在二维矩形面积与周长计算中的应用

核心逻辑与数学原理

扫描线算法（Scanning Line）是线段树在二维几何计算中的核心应用。其经典问题是：在平面直角坐标系中，给定 $N$ 个边平行于坐标轴的矩形，求它们的面积并或周长并。

1. 空间切片与维数裁剪

直接求解二维图形的面积并需要处理极其复杂的边界相交情况。扫描线算法的核心思想是降维分治：用一条垂直于 $x$ 轴的直线（扫描线）从左向右（或垂直于 $y$ 轴从下向上）平移。

矩形的左右两条垂直边被抽象为扫描线上的事件点（Event）：

左边（入边）：矩形区域开始，标记值为 $+1$。
右边（出边）：矩形区域结束，标记值为 $-1$。

若将所有矩形的左右边按 $x$ 坐标升序排列，整个二维平面就被切割成了 $2N-1$ 个垂直不相交的纵向条带。对于第 $i$ 个条带，其宽度为 $\Delta x = x_{i+1} - x_i$，其高度 $H$ 为当前扫描线截得的所有有效纵向线段的长度并。则该条带的面积为：

$$ \Delta S = \Delta x \times H $$

最终的总面积即为所有条带面积的代数累加：$S_{all} = \sum \Delta S$。

2. 离散化与区间连续性映射

由于纵坐标 $y$ 的值域通常极大（如 $10^9$）或者是实数，无法直接作为线段树的数组下标。必须将所有矩形的纵坐标 $y$ 提取、去重、升序排序，映射到一个大小为 $M$ 的离散化数组 $raw\text{ }y$ 中。

绝对致命考点：线段树的节点维护的是区间（线段长度），而不是点。若离散化后有 $M$ 个唯一的 $y$ 值，它们将组成 $M-1$ 个基本线段。线段树的叶子节点 $u$ 如果代表闭区间 $[l, r]$，它在几何上物理映射的实际纵向区间是 $[raw\text{ }y[l], raw\text{ }y[r+1]]$。因此，线段树的根节点维护的区间是 $[1, M-1]$。

状态设计与算法推导

1. 扫描线事件结构体设计

每个矩形贡献两条纵向线段，定义为 ScanLine：

x：线段的横坐标（用于排序触发扫描）。
y1, y2：线段的纵坐标区间（满足 $y1 < y2$）。
mark：入边为 $1$，出边为 $-1$。

2. 线段树节点状态设计

不同于基础线段树，标准扫描线由于其特殊的对称加减性（入边 $+1$，出边 $-1$），不需要引入标准 pushdown 懒标记机制。每个节点 $u$ 维护两个核心状态：

cover[u]：当前区间被完全覆盖的次数（若 cover[u] > 0，说明该节点代表的几何区间被整体激活）。
len[u]：当前区间内被覆盖的实际几何线段长度。

3. 特化的 `pushup` 控制逻辑

由于没有 pushdown，一个节点的数据正确性完全由自身的 cover 和子节点的 len 决定。当执行 update(u, l, r, ql, qr, val) 导致 cover[u] 改变时，立即通过特化的 pushup 重新计算 len[u]：

$$ len[u] = \begin{cases} raw\text{ }y[r+1] - raw\text{ }y[l], & \text{if } cover[u] > 0 \ len[u \ll 1] + len[u \ll 1 | 1], & \text{if } cover[u] = 0 \text{ and } l < r \ 0, & \text{if } cover[u] = 0 \text{ and } l = r \end{cases} $$

逻辑解释：如果当前节点 cover > 0，说明该区间被完全覆盖，直接计算其几何跨度；如果 cover == 0 且不是叶子节点，其几何长度由左右子节点汇报的和决定；如果是叶子节点且 cover == 0，长度为 $0$。

C++ 标准源码（NOIP风格）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

inline long long read() {
    long long x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int MAXN = 200005; // 2个矩形贡献4条边，空间必须开到 2 * N 的 4 倍

struct ScanLine {
    long long x;
    long long y1, y2;
    int mark;
    // 严格按横坐标升序排序，x 相同先处理入边（mark大者优先）防止边界断层
    bool operator<(const ScanLine& b) const {
        if (x != b.x) return x < b.x;
        return mark > b.mark;
    }
} line[MAXN << 1];

long long raw_y[MAXN << 1];
long long len[MAXN << 3];  // 致命踩坑点：由于点数翻倍，线段树空间须为 MAXN * 8
int cover[MAXN << 3];

// 特化无标记 pushup 机制
inline void pushup(int u, int l, int r) {
    if (cover[u] > 0) {
        len[u] = raw_y[r + 1] - raw_y[l]; // 映射几何物理区间
    } else if (l == r) {
        len[u] = 0; // 叶子节点且未覆盖
    } else {
        len[u] = len[u << 1] + len[u << 1 | 1];
    }
}

// 核心几何区间更新：传入的 ql, qr 必须是离散化数组的下标区间
void update(int u, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        cover[u] += val;
        pushup(u, l, r); // 覆盖状态改变，立刻计算当前节点实际长度
        return;
    }
    int m = (l + r) >> 1;
    if (ql <= m) update(u << 1, l, m, ql, qr, val);
    if (qr > m) update(u << 1 | 1, m + 1, r, ql, qr, val);
    pushup(u, l, r);
}

int main() {
    int n = read();
    int cnt = 0;
    for (int i = 1; i <= n; ++i) {
        long long x1 = read(), y1 = read(), x2 = read(), y2 = read();
        line[++cnt] = {x1, y1, y2, 1};
        raw_y[cnt] = y1;
        line[++cnt] = {x2, y1, y2, -1};
        raw_y[cnt] = y2;
    }

    // 离散化纵坐标
    sort(line + 1, line + cnt + 1);
    sort(raw_y + 1, raw_y + cnt + 1);
    int tot = unique(raw_y + 1, raw_y + cnt + 1) - (raw_y + 1);

    // 线段树维护的是区间，tot个点对应 tot - 1 个闭区间
    // 根节点维护区间为 [1, tot - 1]
    long long ans = 0;
    for (int i = 1; i < cnt; ++i) {
        // 在离散化数组中二分定位纵坐标区间的下标
        int ql = lower_bound(raw_y + 1, raw_y + tot + 1, line[i].y1) - raw_y;
        int qr = lower_bound(raw_y + 1, raw_y + tot + 1, line[i].y2) - raw_y - 1; // 致命踩坑点：右边界映射必须减 1

        if (ql <= qr) {
            update(1, 1, tot - 1, ql, qr, line[i].mark);
        }
        ans += len[1] * (line[i + 1].x - line[i].x);
    }

    printf("%lld\n", ans);
    return 0;
}

NOIP 实战避坑指南

1. 线段树右边界映射未减 1 导致计算越界

离散化后，线段树叶子节点 $i$ 代表的是几何区间 $[raw\text{ }y[i], raw\text{ }y[i+1]]$。若一条扫描线的纵向范围是 $[raw\text{ }y[A], raw\text{ }y[B]]$，在线段树中进行 update 的目标区间是 $[A, B-1]$。如果错误地传入了 $[A, B]$，当 update 触及到第 $B$ 个节点时，pushup 公式中的 raw_y[r+1] 将访问 raw_y[B+1]，引发严重的逻辑越界或读入垃圾数据。

2. 空间开辟倍数严重计算不足

普通线段树开 $4$ 倍空间。但在扫描线算法中，输入 $N$ 个矩形，会产生 $2N$ 条边和 $2N$ 个纵坐标点。这意味着原数组的基数已经变成了 $2N$。因此，线段树的数组大小必须开到 $2N \times 4 = 8N$。仅开 $4N$ 会导致在建树或更新到右侧子树深层时直接 RE。

3. 横坐标排序时未处理并发边界

当两个矩形的横坐标重合（即 $x_1 = x_2$）且一条为入边（$+1$）、一条为出边（$-1$）时，若错误的先处理了出边，线段树对应的 len[1] 会瞬间断崖式降为 $0$，紧接着处理入边又升回来。这会导致在计算 $\Delta x \times len[1]$ 时乘上了一个错误的中间零值。必须在结构体重载 < 时，强制规定 $x$ 相同时入边优先。

经典 NOIP/洛谷真题

1. 洛谷 P5490 【模板】扫描线 & 矩形面积并

题意描述：求 $N$ 个设在平面直角坐标系中的矩形互相覆盖后的总面积。
问题本质：标准的二维离散化扫描线算法基准落地题。
核心解题思路：如源码所示，将 $y$ 轴坐标抽取离散化为树的节点区间。横坐标作为事件点驱动扫描线从左向右平移。利用不带 pushdown 的特化线段树，在 $O(N \log N)$ 复杂度内完美解决高维连续空间向低维离散空间的映射求和。

2. 洛谷 P1856 [IOI1998] [USACO5.5] 矩形周长 Picture

题意描述：求 $N$ 个矩形组合图形的整体外轮廓周长总和。
问题本质：扫描线的高阶应用，需要同时维护区间覆盖线段长度以及不相交线段的段数。
核心解题思路：周长由横向边和纵向边共同组成。可以使用两次扫描线分别处理，或者在单次垂直扫描中同时解决：线段树节点不仅要维护 len（覆盖长度），还要维护 num（当前区间包含多少条独立的纵向线段）以及 l_count, r_count（左右端点是否被覆盖）。每次扫描线推进时，纵向边的贡献为 $|len_{new} - len_{old}|$，横向边的贡献为 $2 \times num \times \Delta x$。