AcWing 1228. 油漆面积
一、相关资源
https://www.bilibili.com/video/av374239033
大佬题解
二、标准解法
对于这种题我们的正解就是线段树套扫描线，听起来是不是逼格很高。
三、扫描线概念
什么是扫描法？有什么用？怎么用？
可以想象成一根假想的线，将图从左往右或从右往左或自下而上或自上而下“扫描”一遍，至于扫描的是什么则根据具体应用选择。
扫描线可以计算矩形面积、周长，可以计算线段交点，可以实现多边形扫描转换，在图的处理方面经常用到。
这里总结一下扫描线计算矩形面积的算法。
怎么用？首先，对于之前的图，除了用总面积减去重合面积，还可以换一种计算方法，如图：
此图用\(4\)条横线将整个图划分成了\(5\)个部分，显然此时再算面积就可以用各个颜色的部分求和。
想想，这样计算的整个过程：
假设我们的视线自下而上，首先，我们看到了最下面灰色矩形的下边，
用这个下边的长度乘以这条边和上一条边的高度差即得到灰色矩形面积，
继续看到蓝色的矩形的下边，虽然蓝色矩形有两个，但我们计算时自然会用结合律将两个矩形的下边加起来再去乘以同样的高，然后重复这样的操作，我们最终可以求得整个图形的面积。
四、扫描线的计算机实现
但是，这依旧是人做的，计算机要怎么实现呢？首先的问题是，计算机要怎么保存这张图这些矩形？
从刚才的过程，我们不难发现，我们只需要保存这张图里面的所有水平的边即可。
对于每条边，它所拥有的属性是：这条边的左右端点（的横坐标），这条边的高度（纵坐标），这条边属于矩形的上边还是下边（想想为什么保存这个属性）
刚刚计算中我们遇到两个蓝色矩形的一部分一眼就能看出这两个蓝色矩形的 宽 是多少，用计算机怎么做到？
线段树华丽登场!
我们以整个图最左边的竖线作为区间左端点，最右边的竖线作为区间右端点，去维护这个区间的有效长度（即被覆盖的长度）
比如扫到第\(2\)条边的时候，有效长度就是两个蓝色矩形的宽之和。
这样，我们用扫描线去扫描每一条边的时候，都需要更新线段树的有效长度
是如何更新的呢？
如果扫到的这条边是某矩形的下边，则往区间插入这条线段
如果扫到的这条边是某矩形的上边，则往区间删除这条线段
为什么？自己试着模拟一下就不难发现：
因为我们是自下而上的扫这个图，扫到下边相当于刚刚进入一个矩形，扫到上边则是要离开一个矩形
利用线段树把每条边的有效长度找到了，也就是找到了每部分的所有矩形的总宽，那么高呢？
高就简单多了，对于所有的边，按照高度从小到大排列，那么矩形高就是每相邻边之间的高度差
五、手推一波
- 扫描线扫描的过程（建议配合代码模拟）
初始状态
扫到最下边的线,点更新\(1~3\)为\(1\)
扫到第二根线,此时将计数器不为\(0\)的长度*上线两根线的长度,得到绿色的面积,加到答案中去.随后更新计数
同上,将黄色的面积加到答案中去
同上,将灰色的面积加到答案中去
同上,将紫色的面积加到答案中去
同上,将蓝色的面积加到答案中去
六、本题相关知识点
扫描线
可以看成一根平行于\(x\)轴的直线,从\(y=0\)开始往上扫,直到扫出最后一条平行于\(x\)轴的边。但是真正在做的时候,不需要完全模拟这个过程,扫描线的做法是从最下面的边开始扫到最上面的边。
线段树
本题用于动态维护扫描线在往上走时,\(x\)哪些区域是有合法面积的。
七、实现代码
#include
using namespace std;
const int N = 1e4 + 10;
struct Segment {
int x, y1, y2; // x为横坐标，y1,y2为线段树维护的两个纵坐标,这样设计的扫描线，是从左到右竖着的扫描线
int k; // k表示我们要加的权值，为+1或-1
bool operator<(const Segment &t) const { //由于要把所有的线段按照横坐标排序，所以要重载小于号
return x < t.x;
}
} seg[N * 2]; //线段最多有两倍(每个矩形两条竖边)
struct Node {
int l, r;
int cnt; //区间被覆盖的次数
int len; //这条竖线上至少被覆盖一次的区间总长度
} tr[N * 4];
//利用子节点信息更新父节点信息
void pushup(int u) {
if (tr[u].cnt > 0)
tr[u].len = tr[u].r - tr[u].l + 1; //多次被更新的时候，代表这条线是被重复覆盖的，所以直接左右边界相减即可
else if (tr[u].l == tr[u].r)
tr[u].len = 0; //默认线段树的叶节点长度为为0
else
tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len; //第一次更新的时候记录长度
}
void build(int u, int l, int r) { //建树
tr[u] = {l, r, 0, 0}; //记录这条竖边的上下边界，初始化构建，cnt和len默认为0
if (l == r) return; //递归到线段树的子节点就返回
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
void modify(int u, int l, int r, int k) { //遇到一条新的矩形竖边，就再更新一次
//当前区间已经被完全包含
if (l <= tr[u].l && r >= tr[u].r) {
tr[u].cnt += k; //更新被覆盖的次数
pushup(u);
} else { //往下寻找
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, k);
if (r > mid) modify(u << 1 | 1, l, r, k);
pushup(u);
}
}
int n;
int main() {
cin >> n;
int idx = 0;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
// seg数组是一个结构体数据，装的结构体有三个属性：x,y1,y2,竖着走的扫描线
seg[idx++] = {x1, y1, y2, 1}; //矩形左竖边，1表示矩形来了
seg[idx++] = {x2, y1, y2, -1}; //矩形右竖边，-1表示矩形离开
}
sort(seg, seg + idx); //给所有竖线按照x坐标排序,扫描线从左到右准备出发
//构建线段树
//为什么要使用线段树，它是解决什么问题的呢？
//(1)在扫描线的不断移动过程中，需要知道所有 "覆盖次数" 大于等于 1 的"子线段"(可以理解为切碎的)总和。
//(2)在扫描线的不断移动过程中，对区间的+1，-1需要不断修改
//以上两点概念一下就是：动态修改，区间查询总和，适用线段树的数据结构
build(1, 0, 10000); //最多10000个矩形，1个矩形可以产生一个线段区间，2个矩形最多可以产生2个线段区间...以此类推,最多10000个区间
int ans = 0;
for (int i = 0; i < idx; i++) { //遍历所有竖线
if (i > 0) { //第一条竖边无法计算面积
ans += tr[1].len * (seg[i].x - seg[i - 1].x); //根结点的len * 阴影部分高度
}
modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k); //维护的是一小段区间
}
//输出结果
cout << ans << endl;
return 0;
}
八、与普通线段树+懒标记的区别
它与一般有懒标记的线段树有一下几个区别：
- 扫描线中每个点代表的是一个线段，具体到这个题中就是每次给我们一个矩形的信息，我们可以对它构建出一个三元组\(（x1,y1,y2)，(x2,y1,y2)\),如下图所示:
其中记录x的作用是用来确定当前扫描线被计算的顺序的，\(y1\),\(y2\)可以用来表示当前的那一段要进行覆盖，在\(x1\)处要对\([y1,y2-1]\)这一段的覆盖次数加一，表示被覆盖，在\(x2\)处减一，解除覆盖，注意这里为什么是\(y2-1\),前面说过这里的点代表的是实际中的线段，可以通过下面的图来理解:
给定的是点的标号，也就是图上下面的\(y1,y2\)，而我们写代码用到的是上面的表示线段的的\(y1,y2\)
- 标记不会向下更新，当更新到当前线段树时如果刚好包括当前节点的所表示的一段，那对当前节点更新后，就不会向下更新，为啥？因为我们最终需要的答案始终是由根节点提供的，当前节点更新后，只需要向上层节点回溯到根节点即可，不必向下更新。
做法就是先根据\(x\)坐标对得到的三元组进行排序，更新答案（答案加上根节点中被覆盖的区间长度*当前\(2\)条扫描线之间的宽度），然后进行上面第\(1\)点提到的操作。