【基础算法】扫描线+线段树,求矩形面积并

发布于 2022-10-06  648 次阅读


在做矩形面积并之前需要了解线段树,不了解线段树的需要先对线段树的各种操作比较熟练后,方可学习扫描线。

线段树资料:

线段树 - OI Wiki (oi-wiki.org)

线段树详解 - 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。

将X的小段进行标号

为什么需要这么做呢,就是为了保持线段树节点管辖区间之间的连续性,我们可以发现在做小段编号之后,区间[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;
}