企业官网建设流程全解析

最近又把扫描线+线段树这套经典模板过了一遍，做的是P5490这道矩形面积并模板题。很多题解代码贴出来容易，但线段树节点到底在维护什么、为什么修改时不需要pushdown、离散化之后区间编号怎么映射，讲清楚的其实不多。我最早在这个模板上卡了很久，回头想想就是没把“区间段”和“点”这两件事分开。这篇把我自己的完整推导、可AC代码和踩过的坑一起整理出来，给后面入坑扫描线的同学一个可以直接抄作业的版本。

1. 扫描线：把二维面积并问题拍扁成一维

1.1 为什么不能直接算并集面积

矩形面积并最大的麻烦是重叠区域不能重复计算。最朴素的想法是把所有矩形并集按二维网格切碎，逐格累加，但坐标范围到了1e9，完全没法开数组。用容斥枚举矩形组合也行，但矩形数量到1e5时集合组合是爆炸的，完全不可行。

扫描线能解决这个问题，是因为它把“二维图形求面积”降成了“一维区间维护”。想象有一根竖着的尺子从左往右扫过整个平面，任何时刻尺子与矩形并集相交的部分，是一段一段的纵向区间。尺子每向右移动一点点，扫过的面积就等于“移动宽度 × 当前尺子与并集相交的总长度”。这就是微积分里面积分的基本思想，只不过离散化之后变成了分段求和。

1.2 事件列表与矩形拆边

具体实现时不需要真的让尺子连续移动。矩形对总面积的影响只在其左右边界处发生变化：左边界进入一个矩形，右边界离开一个矩形。因此把每个矩形拆成两条竖边：

struct Line { long long x; long long y1, y2; int state; // 1 表示左边界，-1 表示右边界 };

两条边的x坐标分别是x1和x2，纵向范围都是[y1, y2]。state标记这条边是“进入”还是“离开”。把所有边按x从小到大排序，然后扫一遍。每次扫到一条边，说明从上一个x到当前x这一段区域内，有效y覆盖没有发生变化，于是先把答案累加上：

[ \text{ans} += \text{当前有效y总长度} \times (x_i - x_{i-1}) ]

然后根据当前边的state，在线段树里把区间[y1, y2]的覆盖次数+1或者-1。

1.3 事件排序的细节

排序只有两个点需要注意。第一，x相同的情况很常见，比如两个矩形的边界刚好共线。第二，循环里必须“先累加答案，再更新线段树”，这样同一x上的多条边逐个处理时，它们之间的宽度差是0，不会错误增加面积。我当时第一次写的时候是先更新再累加，结果同一竖线上的多条边会把中间某个中间态的长度乘上一个0宽，虽然理论上x差为0不会出错，但如果实现时更新和累加的顺序反了，就容易写顺手写出别的问题。稳妥的做法就是上面那个顺序：

for (int i = 1; i <= lineCnt; i++) { if (i > 1) ans += tree[1].len * (lines[i].x - lines[i - 1].x); // 再更新当前边 }

2. 线段树维护“当前被覆盖的y总长”

2.1 朴素覆盖表为什么不行

扫到一条竖边时，需要支持“把y区间[y1, y2]的覆盖次数整体加1或减1”，并且随时要能拿到“当前所有y坐标中被覆盖过的总长度”。如果y范围小，可以直接用差分数组，每个单位长度记录被覆盖次数，覆盖次数大于0就算进入总长。但y坐标是1e9量级，必须离散化。

离散化不是简单地把点排序。这里非常容易混淆：线段树的叶子节点不能表示“第几个离散化后的y坐标点”，而要表示“相邻两个离散化y坐标之间的区间段”。因为面积计算要的是长度，不是点的个数。

离散化之后有m个互不相同的y值，那么本质上存在m-1个区间段：第i段表示[ys[i], ys[i+1])。线段树叶节点下标i对应这一段。一个节点如果被完全覆盖，它的贡献长度就是：

ys[r + 1] - ys[l]

其中l和r是这个节点管辖的段编号范围。这是整题的核心映射，后面所有代码都围绕它展开。

2.2 覆盖次数与长度分开记录

线段树节点需要维护两个东西：

• cover：整个节点对应区间被完整覆盖的次数。
• len：这个节点对应区间中，当前被覆盖的总长度。

每次更新一条边时，找到该边y1、y2对应的段编号区间，然后整体加上state（+1或-1）。更新到完全覆盖的节点时，只修改这个节点的cover，不继续向下递归。

关键点来了：cover和len之间是这样一个关系：

void pushUp(int u, int l, int r) { if (tree[u].cover > 0) { tree[u].len = ys[r + 1] - ys[l]; } else if (l == r) { tree[u].len = 0; } else { tree[u].len = tree[u << 1].len + tree[u << 1 | 1].len; } }

当cover大于0，说明整个节点管辖区间都被覆盖，长度直接是整个区间的实际长度；覆盖次数为0时，长度由左右儿子汇总。这个pushUp在每次update后被调用，保证父节点信息正确。

2.3 为什么不需要pushdown

这是扫描线线段树和普通区间修改线段树最不一样的地方。普通线段树修改区间后，查询子区间时需要把懒标记下推；扫描线的线段树却完全不用pushdown，甚至下推会出问题。

道理在于“覆盖+1”和“覆盖-1”的事件一定是成对出现的。一条左边界加入矩形，就必然有一条右边界把它删掉。可以把cover理解成一个“递归括号”：某个节点的cover为正，只表示整个段被一些矩形整体罩住，罩住它并不代表它下面的子区间没有自己的额外覆盖状态。

假设父节点cover从1变成2，子节点信息不会被改动；等父节点cover减回0时，pushUp中会重新取左右儿子的len之和。由于儿子节点的cover虽然是“陈旧”的，但它们在各自被完整覆盖/删除的过程中已经维护好了自己的len，所以汇总结果是正确的。

用个生活类比：文件夹被整体打包占用时，不需要关心里面的每个子文件；文件夹一旦释放，里面的文件原本是什么状态就还是什么状态，信息不会丢。如果在这个场景里强行pushdown，反而会把“整体覆盖”的状态错误地压到每个子区间，后续删除时很难分清哪些是整体添加的、哪些是子区间自身添加的，麻烦且低效。

2.4 更新区间的下标映射

设离散化后有m个不同的y坐标，下标从1到m。那么线段树维护的段编号范围是1到m-1。一条边事件给出[y1, y2]，先映射：

int l = lower_bound(ys + 1, ys + m + 1, y1) - ys; int r = lower_bound(ys + 1, ys + m + 1, y2) - ys;

这里l和r是y坐标在离散化数组中的下标。要覆盖的是从段l到段r-1，所以更新时传入的参数是：

update(1, 1, m - 1, l, r - 1, state);

这个r-1也是新手特别容易踩的坑。忘减1，就会多覆盖一段，导致答案偏大。

3. 完整可AC的实现：一条条拆开讲

3.1 完整代码

先给出我能稳定通过的C++写法，再逐段解释。这种写法基于递归线段树，清晰不容易出错。

#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 100010; struct Line { ll x; ll y1, y2; int state; bool operator < (const Line& other) const { return x < other.x; } } lines[MAXN * 2]; int n; ll ys[MAXN * 2]; int yCnt; struct Node { int cover; ll len; } tree[MAXN * 8]; void pushUp(int u, int l, int r) { if (tree[u].cover > 0) { tree[u].len = ys[r + 1] - ys[l]; } else if (l == r) { tree[u].len = 0; } else { tree[u].len = tree[u << 1].len + tree[u << 1 | 1].len; } } void update(int u, int l, int r, int L, int R, int v) { if (L <= l && r <= R) { tree[u].cover += v; pushUp(u, l, r); return; } int mid = (l + r) >> 1; if (L <= mid) update(u << 1, l, mid, L, R, v); if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, v); pushUp(u, l, r); } int main() { scanf("%d", &n); int lineCnt = 0; for (int i = 1; i <= n; i++) { ll x1, y1, x2, y2; scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2); lines[++lineCnt] = {x1, y1, y2, 1}; lines[++lineCnt] = {x2, y1, y2, -1}; ys[++yCnt] = y1; ys[++yCnt] = y2; } sort(lines + 1, lines + lineCnt + 1); sort(ys + 1, ys + yCnt + 1); int m = unique(ys + 1, ys + yCnt + 1) - (ys + 1); ll ans = 0; for (int i = 1; i <= lineCnt; i++) { if (i > 1) { ans += tree[1].len * (lines[i].x - lines[i - 1].x); } int l = lower_bound(ys + 1, ys + m + 1, lines[i].y1) - ys; int r = lower_bound(ys + 1, ys + m + 1, lines[i].y2) - ys; update(1, 1, m - 1, l, r - 1, lines[i].state); } printf("%lld\n", ans); return 0; }

3.2 数组大小为什么开8倍

线段树的常规数组大小是4倍节点数。这里y坐标最多有2n个，离散化后m最大是2n，那么段数m-1最多是2n-1。递归线段树节点编号上界是4*(m-1)，约等于8n。因此开MAXN * 8最稳，有些题解里习惯直接开MAXN << 3，是一个意思。如果只开4n，数据一大就会在递归越界时出现莫名其妙的随机错误，表现可能是答案偏大或者直接segmentation fault。

3.3 关于lower_bound映射的说明

因为所有y坐标都来自输入，一定在ys数组中存在，所以lower_bound一定找得到准确位置，不会出现找不到的情况。但要注意这里的ys是1-based数组，lower_bound返回的迭代器减去ys指针后，得到的就是1-based下标。我用ys + 1开头，m是最后一个有效位置。

3.4 面积和用long long的原因

坐标范围到1e9，n到1e5，极端情况下所有矩形并排，面积可以达到1e14级别。int完全存不下，答案变量ans、线段树里的len、结构体里的坐标都必须是long long。cover因为是覆盖次数，最多累加到n，用int足够。

4. 手算一个例子：两个重叠矩形

4.1 问题设定

现在用一个非常小的例子把整个过程走一遍，这个例子也可以用来验证你的代码。

矩形A：左下角(0,0)，右上角(4,3)。宽4，高3。 矩形B：左下角(2,1)，右上角(6,5)。宽4，高4。

两个矩形重叠区域为x[2,4]，y[1,3]，重叠面积2×2=4。所以总面积是12+16-4=24。

把所有边列出来并排序：

离散化后ys数组为[0,1,3,5]，m=4，段编号1到3，分别对应区间[0,1)、[1,3)、[3,5)。

4.2 逐步扫描过程

初始线段树全0，tree根节点len为0。

处理第一条边x=0，state=+1： 按照循环顺序，i=1时不累加答案。 update覆盖y段[0,3)即段编号1到2。 覆盖后：段[0,1)和[1,3)被覆盖，树根len=3。 此时ans=0。

处理第二条边x=2，state=+1： 先累加，当前len=3，宽度是2-0=2。 ans=0+3×2=6。 这对应从x=0到x=2，左侧只有矩形A覆盖y长度3。 然后update覆盖y段[1,5)，即段编号2到3。 现在段[0,1)被A覆盖，段[1,3)被A和B两个矩形覆盖，段[3,5)被B覆盖。树根len=5。

处理第三条边x=4，state=-1： 先累加，当前len=5，宽度是4-2=2。 ans=6+5×2=16。 然后update删除y段[0,3)，段编号1到2。 删除后：段[0,1)不再被覆盖，段[1,3)只剩B覆盖，段[3,5)被B覆盖。树根len=4。

处理第四条边x=6，state=-1： 先累加，当前len=4，宽度是6-4=2。 ans=16+4×2=24。 然后update删除y段[1,5)，段编号2到3。 全部清零，树根len=0。

最终答案是24，和手算完全一致。

这个例子我建议初学者一定要自己跟着推一遍。调试时也可以把每一条边处理后的tree[1].len打印出来，看看是不是按3、5、4、0变化。如果不是，那问题多半出在覆盖区间映射或update区间判断上。

5. 常见错误与调试实录

5.1 高频错误速查

5.2 一个让人印象深刻的同x边界问题

有一类数据会出现很多矩形共用同一个x边界。我的第一版代码是每次update之后才在下一个事件累加宽度，表面上没问题，因为重复x的两次事件之间宽度差是0。但如果你写的是“每次处理事件前直接查询len并乘以与上一个事件x的差”，那么对同一个x的第二个事件，依然会执行一次宽度为0的累加，这没有问题。

真正危险的是另一种写法：先x变化时先把len乘当前x和lastx的差累加，然后才处理完这一列的所有事件。如果照这种写法，同一x上的事件没有被合并，就会出现有的边界还没处理完就累加了一次宽度为0的中间态。虽然宽度差是0，结果理论不变，但代码里很容易在排序不完全或者去重不完全时混入脏数据。最简单可靠的顺序就是先前文写的那样：每条边分别处理，但一律“先累加、后更新”。

5.3 用随机小数据验证正确性

刷模板题验证代码，最有效的办法是自己写一个针对小范围的暴力求解函数。对于随机生成的n个小矩形，坐标范围例如0到10，暴力做法就是枚举每一个单位小方格，看它是否落在任意矩形内部，统计总格数，然后用这个结果和扫描线代码的结果比对。

为了让坐标是整数且方便枚举，暴力时可以把每个整数坐标点当作格点中心，也可以直接用闭区间判断：对每个单位正方形(x从0到9, y从0到9)检查是否存在某个矩形完全包含这个单位正方形。多跑几百组随机数据，能快速暴露区间映射、边界处理这类问题。

6. 延伸思考与个人经验

6.1 从面积并到周长并

掌握了面积并这套模板，矩形周长并的题也就顺理成章。周长并除了维护当前总覆盖长度，还要维护覆盖段数。前者决定竖线方向贡献的周长，后者决定横线方向贡献的周长。扫描线的思想完全一样，差别只在pushUp时需要多更新一个segCnt字段：当一个节点的cover大于0，segCnt等于1；叶子节点为0；其他情况由左右儿子segCnt相加，但如果左右儿子都有覆盖且中间是连着的，需要减1。这类变式本质上就是扫描线下维护不同的统计量。

6.2 为什么用离散化而不是动态开点

很多刚开始学扫描线的同学会问：坐标1e9，为什么不用动态开点线段树，省掉离散化？动态开点确实可以，每次update在递归路径上新建节点，总节点数大约是O(nlogn)。但常数比离散化版大不少，而且本题已经有现成的离散化坐标，代码复杂度并没有增加多少。离散化之后用静态数组更快更稳，竞赛里我基本都是先离散化再建树。

6.3 我对这道模板题的最终体会

再回过头说说这题最难的地方。难点不在线段树模板本身，而在“把区间段和坐标点分开”的建模思维。我第一次做的时候直接把叶子节点当作离散化后的y坐标点，于是len怎么算都对不上，最后才知道要把相邻两个y坐标之间的区间当作一个基本单位。边界是否算入面积这件事也不用太纠结，因为连续平面图形的边界线对面积没有贡献，所以离散化区间用左闭右开或者闭区间，结果都一样。理解了这一点，很多关于边界的疑惑都会自然消失。

最后分享一个小习惯：每道扫描线模板题，我都先用上面那个两个矩形重叠的例子手动推一遍，再用随机小数据暴力对拍。这套流程走下来，代码里的低级错误基本能一次清干净。希望这篇总结能帮你在扫描线上省下我之前踩坑花掉的时间。