丈量遗城

穿过高架桥，是一片废墟——不是被炸毁的，是被时间遗忘的。断壁残垣之间，散落着无数块能量地毯。每块地毯有一个矩形覆盖区，颜色各异。Echo说这些地毯是Zero曾经划分的势力范围，现在要丈量它们的总面积。

"不能一块一块量。"你说，"很多地毯重叠了，直接加会重复计算。"

"那咋个办？"CC问。

"铺卷尺。"你说，"从左走到右，每遇到一块地毯的左边界，就把它铺开的上下范围记下来；每遇到右边界，就把那片范围收起来。一路上，随时量当前铺开的地毯有多宽。"

"上下范围又咋个管？"

"建一个分层台账。"你说，"把整个上下空间切成很多小段，每段记录当前有多少层地毯覆盖。铺开一层就加一，收起来一层就减一。查总宽度时，只需要把覆盖数大于零的段加起来。"

你开始写。先把所有地毯的左右边界取出来，按x坐标排好。然后从最左边开始推进，每遇到左边界，就在分层台账里把对应的上下范围加一；每遇到右边界，就减一。每一步都查询台账里有多少段的覆盖数大于零，乘以当前的横向步长，累加进总面积。

屏幕上跳出了结果。总面积：4747。

"又是47。"CC说。

"4747。"Echo说，"Zero用这个数字标记它的核心势力范围——超过这个面积，就意味着进入了它的真正领地。"

"我们现在在哪？"

"刚好4747。"Echo说，"边界上。"

题目描述

平面上 $n$ 个矩形，求它们的并集面积。

输入格式

$n$。然后 $n$ 行，每行矩形的左下角和右上角坐标。

输出格式

并集面积。

输入样例

2
1 1 3 3
2 2 4 4
0

输出样例

Test case #1
Total explored area: 7.00

提示

• 扫描线 + 线段树。
• 按x坐标排序，从左到右扫描。
• 线段树维护y轴方向的覆盖长度。

废墟的尽头，是一座信号塔——不是普通的塔，是由无数频段叠加而成的共振柱。Echo说这座塔在发射一种持续的脉冲波，每一段脉冲的强度都不同。

"要截取最强的一段连续脉冲。"Echo说，"不是单个峰值——是连续的一段，总和最大。"

"就像……"CC想了想，"在一段杂音里找最响的连续哼唱？"

"对。"你说，"从左到右听，累加当前的音量。如果累加变成了负数，说明前面的都是噪音，重新开张。"