Coding is the closest thing we have to superpower !

3720 : 线段树-扫描线【模板】
描述

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

对于 100% 的数据,1≤n≤10^5,0≤x_1 < x_2≤10^9,0≤y_1 < y_2≤10^9

输出

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

样例

输入

2
100 100 200 200
150 150 250 255

输出

18000
标签
语言:
主题: