笔记汇总

扫描线，解决的是 按顺序扫描一张图 的问题，若朴素，时间复杂度较高。

如果，这张图上有一些关键图形，我们则可以着重扫描这类信息，从而减少时间。

但是，如果这些图形信息有一些多元关系，就要求我们得枚举所有信息依次判断，增加时间。

在一维判断中，排序有时可以降低了这类问题的时间。

二维，显然是等同的，但若是建轴，较于一维，非同类信息会增加。

故而找到这些信息的关系，是至关重要的。

沿轴的信息，已被排序，通常较好划分出去。

另一维则困难一些。

这时，我们要读懂什么时候会增加，什么时候会减少（或许与沿轴信息有关）。

但请记住，这一维的信息是乱的，我们不能直接 加入答案，（免得违反信息关系）

而是 先储存 以便之后 判断，最好是简单信息。

所以，要找一个媒介进行快速记录（同样也能记录其它信息）。

我们选择了线段树，同时，选用 差分法 在轴方向确定边界。

矩形

排序（离散）、$x$方向建轴、$y$方向建线段树、记录$y$方向关系、应用差分法，按$x$方向枚举。

矩形面积

由上，我们可以知道在$x$轴一点上，$y$段上有多少被矩形占据。

最终，按$x$方向顺序枚举（矩形横向信息），由面积公式算出答案。

矩形周长

我们可以轻松求出所有矩形的宽之和，当然也可以同理求出长之和。

但同学们肯定对此不屑一顾，所以，我讲点难的。

我们知道，扫描线是以$x$轴为基平移的，如果，我们知道扫描线每次平移覆盖多少线段。

就可以得到答案。

那么，什么时候会覆盖线段，当然是经过这条线左端点，未达右端点时。

这可以在更新线段树同时判断，为了避重，需作为线段树的附加信息。