【模板】扫描线 & 矩形面积并

题目描述

求 $n$ 个四边平行于坐标轴的矩形的面积并。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行每行四个非负整数 $x_1, y_1, x_2, y_2$，表示一个矩形的四个端点坐标为 $(x_1, y_1),(x_1, y_2),(x_2, y_2),(x_2, y_1)$。

输出格式

一行一个正整数，表示 $n$ 个矩形的并集覆盖的总面积。

样例 #1

样例输入 #1

2
100 100 200 200
150 150 250 255

样例输出 #1

18000

数据范围

$$\begin{align*} &\#1：n \in [1,10^2], x_i,y_i \in [0,10^2]\\ &\#2：n \in [1,10^3], x_i,y_i \in [0,10^9]\\ &\#3：n \in [1,10^3], x_i,y_i \in [{-10}^9,10^9]\\ &\#4：n \in [1,10^5], x_i,y_i \in [0,10^9]\\ &\#5：n \in [1,10^5], x_i,y_i \in [{-10}^9,10^9]\\ &\text{For all data: } n \in [1,10^5], {-10}^9 \le x_1 < x_2 \le {10}^9, {-10}^9 \le y_1 < y_2 \le {10}^9. \\ \end{align*} $$