6

发表于 2025-06-03

Week 1

发现之前遗漏（或忘记）的知识点有些多，于是这周好好补一下。

求多个矩形的面积并。

首先易得答案为 $\sum 截线段长度 \times 扫过的高度$

考虑把矩形的横边按照 $y$ 排序。

为了快速计算出截线段长度，可以给横边附上 $1$ 或 $-1$ 的权值，记下边权值为 $-1$ ，上半为 $1$ 。这样按照 $y$ 往上扫时，就可以快速地将已经计算过的删掉。

考虑将每个矩形的边的端点先投影到 $x$ 轴上，对于每个被这些点分割的线段，使用线段树维护现在截线段包不包含这个。那么写一颗区间修改单点查询的线段树即可。