扫描线

我还没学计算几何学这东西干啥

在二维平面中给出 \(n\) 个矩形，对于第 \(i\) 个矩形给出对角坐标 \(x_{1_i},y_{1_i},x_{2_i},y_{2_i}\)，求它们的面积并。

\(1\le n\le 10^5,0\le x_{1_i},y_{1_i},x_{2_i},y_{2_i}\le 10^9\)

主要问题是如何处理两个矩形相交的问题

矩形好就好在它的形状十分规则，我们可以把下面这样一个复合图形分割成许许多多的小矩形。

比如上图这个矩形，就可以分成好几块。

对于每一个块，我们发现其宽是几个矩形所占占据的纵坐标区间，长就是我们划分的块长，首先可以考虑到对整个纵坐标建立线段树，然后做区间合并。按横坐标向后扫描，维护纵坐标是否被覆盖，每次求一遍区间并长度和。

但是再看一下数据范围，就会立刻打消暴力建树的念头。非常非常显然还要再优化。

我们发现瓶颈在于横纵坐标是在是太太太太大了，就在这个上面做文章。

现在我们要把矩形的各个竖边拆开来看，设第 \(i\) 条竖边的横坐标是 \(x_i\)，竖边覆盖的纵坐标区间是 \(l_i,r_i\)。

对于横坐标上的扫描，能发现我们根本不需要每一个横坐标都做一遍求和，事实上在 \(x_i\) 和 \(x_{i+1}\) 之间的区间覆盖情况一定是一样的，也就是说一定是一个矩形，我们可以在 \(x_i\) 做一遍区间并长度和之后直接先乘 \(x_{i+1}-x_i\)。横坐标上的最坏时间 \(10^9\Rightarrow 10^5\)。

对于纵坐标上的维护区间合并。区间合并时，我们其实只会关心区间各个端点的大小关系，类似地沿用上面的方法。我们先把所有的 \(l,r\) 放在一起排序得到数组 \(y\)，在这上面建立线段树，每个节点维护的是 \(y_i,y_{i+1}\) 之间的区间被覆盖的次数，如果我们想要覆盖一个区间 \(L,R\) 的话我们就可以把 \(y_{i_L},y_{i_r-1}\) 区间 \(+1\) 即可。

线段树维护区间覆盖次数和区间长度即可(结果这里还卡了我很久)。