扫描线可以用来求解周长并和面积并。
面积并
扫描线
给定 \(n\) 个长方形，求它们的面积并。下面以两个长方形为例：
对于这个问题，可以有容斥等做法，但是还有个更简单的方法——扫描线。
扫描线，顾名思义，就是，拿一条“线”取扫（这里是从下往上扫，其实其它的扫的方式也是可以的）：
如图所示，这几个图形被四条线分成了 \(3\) 个部分，我们可以对每一个部分的面积计算并累加起来。由于这些部分都是长方形，而这些长方形的宽很好计算，就是线扫过的距离（图中橙色箭头所标），而要求的就是长方形的长。
把每个矩阵的下面的边的值记作 \(1\)，上面的边值记作 \(-1\)，每次经过值为 \(1\) 条边就把对应边加进来，否则删去，那么现在长方形的长就是已加的边组成的边的长度（注意不是所有已加边的长度总和）。
暴力显然是不行的，考虑用数据结构来优化。
线段树优化
观察到，根据矩形的“横边”，可以把整个图形分为 \(3\) 个部分：
可以建一棵线段树来维护这三个部分。
具体的，线段树的每个节点都对应其的一部分，比如节点 \(2\) 对应的就是第一、二部分，节点 \(6\) 对应的就是第三部分。每个节点又维护了两个信息：第一是当前节点被覆盖的次数，第二是当前节点所对应的长方形的长。而长方形的长就是根节点所维护的第二个信息。
为什么要这么维护呢？第二个原因显然，而第一个如果对于每个 \(+1-1\) 的修改，都访问到叶子节点，那么复杂度就爆了，所以在把目标区间拆分成一个个小区间时，就修改区间对应的节点即可（其实有些类似懒标记）。
对应的，线段树要求能从子节点推到父节点，也就是 pushup 操作如下：
int X[N];//X[i] 表示从左往右第 i 条竖边
int tsum[N << 3], tlen[N << 3];//tsum 表示信息一，tlen 表示信息二
void pushup(int k, int l, int r) {//tsum 是由 +1-1 决定的，所以只更新 tlen
if (tsum[k]) tlen[k] = X[r + 1] - X[l];//若整个区间都被访问过了则 tlen 为对应的区间长度
else tlen[k] = tlen[k << 1] + tlen[k << 1 | 1];//否则为左右节点的长方形长之和
}
注意，在 pushup 中，包括之后的所有操作，节点 \(k\) 在线段树中维护的区间为 \([l,r]\)，实际的区间为 \([X_l,X_{r+1}]\)（其实这个操作就是离散化），\(r\) 要加一是因为否则叶子节点维护的就是一个点了。
接下来是 updata。其实就是对每一条线段对应的区间进行更新，不过要注意边界的问题（其实可以这么想，区间对应的 \(l,r\) 是线段左端点的范围）：
void updata(int k, int l, int r, int L, int R, int v) {
//注意区分这里的 L, R 指的是实际的区间而不是 X 的下标
//而 l, r 是指在 X 中的下标范围
if (L <= X[l] && X[r + 1] <= R) {//在区间内就直接更新 tsum
tsum[k] += v;
return pushup(k, l, r);//注意这里也要更新 tlen 因为 tlen 也是受 tsum 影响的
}
int m = l + ((r - l) >> 1);
if (L < X[m + 1]) updata(k << 1, l, m, L, R, v);
//这里和一般的线段树不一样，比如要更新 [1,3]，并不用更新 [3,4] 这个区间，所以不取等号
//还有一点要时刻注意区间 [l,m] 对应 X 的范围是 [l,m+1]
if (R > X[m + 1]) updata(k << 1 | 1, m + 1, r, L, R, v);
pushup(k, l, r);
}
具体的过程还是以上面的例子为例（其中蓝色表示当前更新的边，粉色表示当前长方形的宽，标在节点中的两个数表示 \(tsum\) 和 \(tlen\)）：
然后是删边的两个操作：
PS：其实在实际过程中可以不用更新最后一条边因为更新了也不会被统计到了。
最后是完整的代码（洛谷 P5490 【模板】扫描线），还是要注意边界的问题：
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;//两条边所以开两倍
struct node {
int l, r, h, v;
}Y[N];
int X[N];
bool cmp(node x, node y) {//从下到上排序
return x.h < y.h;
}
int tsum[N << 3], tlen[N << 3]; //这里有个问题就是在 pushup 访问时可能会越界就多开一点
void pushup(int k, int l, int r) {
if (tsum[k]) tlen[k] = X[r + 1] - X[l];
else tlen[k] = tlen[k << 1] + tlen[k << 1 | 1];
}
void updata(int k, int l, int r, int L, int R, int v) {
if (L <= X[l] && X[r + 1] <= R) {
tsum[k] += v;
pushup(k, l, r);
return;
}
int m = l + ((r - l) >> 1);
if (L < X[m + 1]) updata(k << 1, l, m, L, R, v);
if (R > X[m + 1]) updata(k << 1 | 1, m + 1, r, L, R, v);
pushup(k, l, r);
}
signed main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;//注意输入的是先纵坐标后横坐标
X[2 * i - 1] = x1, X[2 * i] = x2;
Y[2 * i - 1] = {x1, x2, y1, 1}, Y[2 * i] = {x1, x2, y2, -1};
}
sort(Y + 1, Y + 1 + 2 * n, cmp);
sort(X + 1, X + 1 + 2 * n);
int len = unique(X + 1, X + 1 + 2 * n) - X - 1, ans = 0;//去重
for (int i = 1; i < 2 * n; i++) {
updata(1, 1, len - 1, Y[i].l, Y[i].r, Y[i].v);//还是注意是 len-1 因为对应的是“左端点”
ans += tlen[1] * (Y[i + 1].h - Y[i].h);//宽度是下一条边高度减当前边高度
}
cout << ans;
return 0;
}
周长并
扫描线
求解周长并同样可以使用扫描线。周长并与面积并类似，不过要分成横边和纵边来计算：
先来考虑比较简单的纵边，而横边则结合着接下来的线段树优化讲。每次扫描，由于两线之间的距离是固定的，所以当前纵边的贡献就是 \(\text{和上条线的距离}\times\text{当前共有几条边}\)。
线段树优化
和面积并一样，周长并也可以使用线段树了，不过会复杂一些（维护的信息更多）。先画出线段树：
然后考虑需要维护哪些信息和如何转移。首先肯定要维护的信息是 \(sum\)，也就是整个区间被覆盖了几次，理由同面积并。其余还是分横边和纵边考虑。
纵边：要维护当前共有几条边，其实就是当前不相交的线段数 \(\times 2\)（也就是把相交的线段“拼”在一起后统计），那么记 \(c\) 为当前区间线段条数，考虑如何转移。
当 \(sum\) 不为 \(0\) 时，其为当前区间长度；否则要从左右儿子转移而来，直接相加肯定不对，因为有一些左右儿子的线段会相交，例如：
左右儿子的 \(c\) 均为 \(1\)，但当前的 \(c\) 也是 \(1\)。
那什么情况下两边线段会相交？观察左右儿子的交界处（左儿子右端点、右儿子左端点），当且仅当它们均被线段覆盖时会相交，\(c\) 需要减 \(1\)，所以再维护一个区间左右端点是否被覆盖 \(lc,rc\) 即可。它们的转移也很简单，\(sum\) 为 \(0\) 时分别为左儿子 \(lc\)、右儿子 \(rc\)，否则均为 \(1\)。
横边：这个和求面积并是长方形的长有点像，要维护当前区间被覆盖的长度 \(len\)。为什么？其实看看答案是什么就一目了然了。观察以下两张图：
其中左图为实际周长的贡献，右图为线段树中的 \(len\)，可以发现，实际周长其实就是两两 \(len\) 之差！这就是为什么要维护 \(len\) 的原因。注意，在统计答案时，还得加上最后的那条横边。
自此，考虑完了以上信息并得出了统计答案的方法，pushup 也很好写了：
struct node1 {
int sum, len, c;
bool lc, rc;
}t[N << 3];
void pushup(int k, int l, int r) {
if (t[k].sum) t[k] = {t[k].sum, X[r + 1] - X[l], 1, 1, 1};
else {
node1 ls = t[k << 1], rs = t[k << 1 | 1];
t[k] = {0, ls.len + rs.len, ls.c + rs.c, ls.lc, rs.rc};
if (ls.rc && rs.lc) t[k].c--;
}
}
在放上最终代码前，总结一下：文章来源：https://www.toymoban.com/news/detail-618063.html
然后就是代码中的细节要注意一下：文章来源地址https://www.toymoban.com/news/detail-618063.html
//洛谷 P1856
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;;
struct node {
int l, r, h, v;
}Y[N];
struct node1 {
int sum, len, c;
bool lc, rc;
}t[N << 3];
int X[N];
bool cmp(node x, node y) {
//如 P5490 第一篇题解所说，由于是求周长，同一高度的边也要按先下边后上边排序
if (x.h != y.h) return x.h < y.h;
else return x.v > y.v;
}
void pushup(int k, int l, int r) {
if (t[k].sum) t[k] = {t[k].sum, X[r + 1] - X[l], 1, 1, 1};
else {
node1 ls = t[k << 1], rs = t[k << 1 | 1];
t[k] = {0, ls.len + rs.len, ls.c + rs.c, ls.lc, rs.rc};
if (ls.rc && rs.lc) t[k].c--;
}
}
void updata(int k, int l, int r, int L, int R, int v) {
if (L <= X[l] && X[r + 1] <= R) {
t[k].sum += v;
return pushup(k, l, r);
}
int m = l + ((r - l) >> 1);
if (L < X[m + 1]) updata(k << 1, l, m, L, R, v);
if (R > X[m + 1]) updata(k << 1 | 1, m + 1, r, L, R, v);
pushup(k, l, r);
}
int main() {
int n;
cin >> n;
for (int i = 1, x1, x2, y1, y2; i <= n; i++) {
cin >> x1 >> y1 >> x2 >> y2;
Y[2 * i - 1] = {x1, x2, y1, 1}, Y[2 * i] = {x1, x2, y2, -1};
X[2 * i - 1] = x1, X[2 * i] = x2;
}
n = n << 1;
sort(Y + 1, Y + 1 + n, cmp);
sort(X + 1, X + 1 + n);
int len = unique(X + 1, X + 1 + n) - X - 1, ans = 0, lst = 0;
for (int i = 1; i < n; i++) {
updata(1, 1, len - 1, Y[i].l, Y[i].r, Y[i].v);
ans += 2 * t[1].c * (Y[i + 1].h - Y[i].h) + abs(t[1].len - lst);//记得加绝对值
lst = t[1].len;
}
cout << ans + Y[n].r - Y[n].l;
return 0;
}
到了这里，关于【学习笔记】扫描线的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
