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

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

求 $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)$。

输出格式

输出一行一个整数，表示这些矩形的并集覆盖的总面积。

样例输入 1

2
100 100 200 200
150 150 250 255

样例输出 1

18000

数据范围

所有测试点均满足：$1\le n\le 10^5$，$0\le x_1<x_2\le 10^9$，$0\le y_1<y_2\le 10^9$。