在做矩形面积并之前需要了解线段树，不了解线段树的需要先对线段树的各种操作比较熟练后，方可学习扫描线。
线段树资料：
线段树详解 - Xenny - 博客园 (cnblogs.com)
好，现在你学会了线段树，接着往下看吧。
扫描线
现在我们用扫描线来求多个矩形组成的一个大图形的面积。
我们先假设有一条从下往上扫描的线（当然你从左往右也一样，后面的操作进行镜像修改即可），这里用一张来自OI Wiki的图来表示我们的扫描过程。
我们并不需要也不能模拟这条线的连续移动，我们只能进行离散的计算，那么我们可以将每一条横线（也就是每个矩形的上底和下底）记录下来作为一个关键帧，每次计算两个关键帧之间的高度距离h和有效的长度len，那么h * len就是一个小矩形的面积，只要将所有小矩形面积加起来就得到了大矩形的面积。
也就是说我们一共需要维护两个量：关键帧（横线）之间的高度距离h、每两个关键帧之间的有效长度len。
我们现在来定义一个横线（线段）的结构体：
struct Seg
{
int x1, x2, h, sign;//sign表示是下底(1)还是上底(-1)
bool operator < (const Seg &m)const{return h < m.h;}//定义排序方法
}s[maxn * 2];//注意开两倍的空间，因为一共N个矩形，就有2N个横线（线段），也就是2N个关键帧
我们将下底的sign设为1，上底的sign设为-1，表示遇到下底我们需要将其所在的小段都加到len里面去，遇到上底就要减掉。
h很容易维护，直接计算两条横线的y差值即可，但是len不太好维护，因为每移动到一个关键帧可能导致某一小段被添加进来或删除，不能直接进行加减因为这里可能有重复添加（覆盖）的小段。上图中的1， 2， 3， 4， 5就表示5个X的小段。
我们需要在移动过程中进行动态的加减，又要考虑覆盖的问题，比如一条线是[x1, x3],另一条线是[x2, x4]，我们不能将长度设为\((x_{3} - x_{1}) + (x_{4} - x_{2})\)，而应该是\(x_{4} - x_{1}\)。
区间的动态操作，容易想到什么？没错，线段树。
我们维护的是一个权值线段树，表示每个X小段被覆盖的次数，当次数大于0的时候被加入到len一次，否则不计算。
线段树中每一个节点都有区间[s ,e]表示这个节点管辖的是第s个小段到第e个小段，既然保存的是小段，就意味着我们需要先将X值进行离散化，我们用下标来表示具体的X值，在线段树中完全不会产生任何和原来的X值有关的操作，仅仅操作离散化后的区间。
下面是离散化的一个示意图。
在对X进行离散化之后，我们还需要对小段进行编号统一，每一个小段的编号和右端点的编号一致，那么如果有一个线段树中的节点管辖区间为[1, 3]，那么意味着这个节点的左右端点为x0和x3，如果这条线被完全覆盖了，这条线贡献的长度就是x3 - x0。
为什么需要这么做呢，就是为了保持线段树节点管辖区间之间的连续性，我们可以发现在做小段编号之后，区间[1, 3]和[4, 5]是连续的。
如果我们的区间表示的不是小段区间而是点区间的话，[1, 3]和[4, 5]就不是连续的，中间缺少了[3, 4]这个区间。
有了这样一个标准之后我们就可以开始操作了。
其实在做扫描线的时候不建树也可以，在每次update的时候检查儿子是否存在并进行动态建树，这里推荐使用动态开点的方法，否则需要开8倍空间甚至更多，如果动态开点的话4倍空间妥妥够（不过也要多两个变量来标记左右儿子）。
节点的定义
struct Node
{
int len, cover;//len表示这个节点贡献的长度，cover表示这个节点是否被覆盖，用于pushup
unsigned ls, rs;//左右儿子，用unsigned可以节省一点空间
}t[maxn * 4];//全局开的变量初始值都是0
int tidx = 1;
tidx就是动态开点的可用内存区的指针，当需要开点的时候就移动tidx，我们默认1号点，也就是根是已经存在的。
离散化的定义
vector<int> X;//离散化
用vector可以方便的进行排序去重。
建树
void build(int s = 1,int e = X.size() - 1, int o = 1)
{
if(s == e)return;//到了叶子退出
if(!t[o].ls)t[o].ls = ++ tidx;//开出左右节点
if(!t[o].rs)t[o].rs = ++ tidx;
int mid = (s + e) >> 1;
build(s, mid, t[o].ls), build(mid + 1, e, t[o].rs);
}
这里值得注意的是初始的e（end）是X.size() - 1，也就是我们上面那张图的小段的右端点（5号小段）。
这个build好像啥也没干，只是把点开出来了，没错确实是这样，所以在update的时候开点也可以，因为全局变量默认都为0，所以也没啥好初始化的。
如果有多组样例注意将tidx初始化为1。
区间修改（在[l, r]的小段上+sign）
inline void pushup(int s,int e,int o)
{
if(t[o].cover)t[o].len = X[e] - X[s - 1];//注意小段和x的编号关系
else t[o].len = t[t[o].ls].len + t[t[o].rs].len;//如果o点未被覆盖，则它的长度是两个儿子的长度之和
}
void update(int l, int r, int v,int s = 1, int e = X.size() - 1,int o = 1)
{
if(l <= s && e <= r)return t[o].cover += v, pushup(s, e, o), void();
int mid = (s + e) >> 1;
if(l <= mid)update(l, r, v, s, mid, t[o].ls);
if(r >= mid + 1)update(l, r, v, mid + 1, e, t[o].rs);
pushup(s, e, o);
}
查找x值在离散化数组中的下标，用于传入到update参数中
inline int bin(int x)//在X数组中找到x的下标
{
return (int)(lower_bound(X.begin(), X.end(), x) - X.begin());
}
完整代码 / Code
例题：P5490 【模板】扫描线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N;
const int maxn = 1e5 + 9;
struct Seg
{
int x1, x2, h, sign;//sign表示是下底(1)还是上底(-1)
bool operator < (const Seg &m)const{return h < m.h;}//定义排序方法
}s[maxn * 2];
struct Node
{
int len, cover;//len表示这个节点贡献的长度，cover表示这个节点是否被覆盖，用于pushup
unsigned ls, rs;//左右儿子，用unsigned可以节省一点空间
}t[maxn * 4];//全局开的变量初始值都是0
int tidx = 1;
vector<int> X;//离散化
void build(int s = 1,int e = X.size() - 1, int o = 1)
{
if(s == e)return;//到了叶子退出
if(!t[o].ls)t[o].ls = ++ tidx;//开出左右节点
if(!t[o].rs)t[o].rs = ++ tidx;
int mid = (s + e) >> 1;
build(s, mid, t[o].ls), build(mid + 1, e, t[o].rs);
}
inline void pushup(int s,int e,int o)
{
if(t[o].cover)t[o].len = X[e] - X[s - 1];//注意小段和x的编号关系
else t[o].len = t[t[o].ls].len + t[t[o].rs].len;//如果o点未被覆盖，则它的长度是两个儿子的长度之和
}
void update(int l, int r, int v,int s = 1, int e = X.size() - 1,int o = 1)
{
if(l <= s && e <= r)return t[o].cover += v, pushup(s, e, o), void();
int mid = (s + e) >> 1;
if(l <= mid)update(l, r, v, s, mid, t[o].ls);
if(r >= mid + 1)update(l, r, v, mid + 1, e, t[o].rs);
pushup(s, e, o);
}
inline int bin(int x)//在X数组中找到x的下标
{
return (int)(lower_bound(X.begin(), X.end(), x) - X.begin());
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//如果有多组样例记得清空X -> X.clear()
cin >> N;
for(int i = 1;i <= N; ++ i)
{
int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;
s[i] = {x1, x2, y1, 1}, s[i + N] = {x1, x2, y2, -1};
X.push_back(x1), X.push_back(x2);
}
sort(X.begin(), X.end());//X排序并去重
X.erase(unique(X.begin(), X.end()), X.end());
sort(s + 1,s + 1 + 2 * N);
build();
int ans = 0;
for(int i = 1;i <= 2 * N; ++ i)//遍历所有关键帧
{
if(i > 1)ans += t[1].len * (s[i].h - s[i - 1].h);//只有i>1的情况才能加到答案里
update(bin(s[i].x1) + 1, bin(s[i].x2), s[i].sign);
}
cout << ans << '\n';
return 0;
}
文章评论