扫描线（离散化线段树）

type

status

date

slug

summary

特点：如果我们需要求的矩形的高度的值域很大，达到了，但是矩形的个数却不是很多，我们可以采用离散化的方法。

如何离散化？

假如给你这两个矩形：

我们可以对这两个矩形的底部与顶部进行排序，得到：

idx	1	2	3	4
val	10	20	30	50

因此，实际上我们只需要对 1 2 3 4 等这四个值进行记录即可，然后把它转变为这样一个线段树：

图中的红色部分就是线段树的节点的左右边界，注意此时对于根节点来说，左右孩子的范围是

我们还需要记录一下原始的数值，因此我们规定代表的就是在这个区间中所代表的数值贡献，即实际区间长度。

我们还需要一个来记录被覆盖了几次，因此我们的线段树的数据结构如下：

经过上面的分析，可以得出创建离散线段树的代码：

对于扫描线，我们创建以下数据结构：

我们首先需要对数据进行离散化，即对输入的矩形的 y 值进行记录然后排序：

首先 line 代表扫描线，对于每一个矩形都有左右两条线，因此我们分别记录它的最低点和最高点，注意还要记录一个 fg ，如果fg为1，则说明刚刚进入这个图形（计算面积）；否则就代表走出了这个图形（不计算面积）。

对于查询所有矩形的面积并，我们可以每次查询相邻两条扫描线之间的距离 * 扫描线所具有的高度贡献，就是每一块矩形的面积，然后累加即可。

例如这两个矩形的求和：

如何查询 扫描线所具有的高度贡献 ？

实际上就是求的值

如果存在区间覆盖，则对扫描线进行区间覆盖次数的计算，判断它是否包含这个图形，然后进行 push_up 操作

push_up操作是核心！

Yuleo