在做矩形面积并之前需要了解线段树,不了解线段树的需要先对线段树的各种操作比较熟练后,方可学习扫描线。
线段树资料:
线段树详解 - 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; }
文章评论