描绘画卷

第二个投影显示的是一幅巨大的画卷——不是纸质的，是光构成的。画卷上有无数条线段，每条线段代表一个事件的持续时间。有些线段重叠，有些不重叠。需要计算这些线段覆盖的总面积。

"铺卷尺。"你说，"把所有线段的上下边提取出来，按高度排序。从上到下扫，维护当前水平方向上被覆盖的长度。"

"又是铺卷尺？"CC问。

"对。但这次是二维的。"你说，"每个矩形有上下两条边。遇到下边就加一层，遇到上边就减一层。分层名册维护每个高度区间被覆盖的次数和实际长度。"

你开始写。先提取所有水平边，按高度排序。然后用分层名册维护高度轴——每个节点存对应区间的覆盖次数和实际长度。扫描时，覆盖次数大于零的区间长度就是实际覆盖长度。

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

"又是47。"CC说。

"4700平方米。"Echo说，"那是我被删除前的缓存区大小。"

题目描述

$n$ 个矩形，求并集的面积。

输入格式

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

输出格式

并集面积。

输入样例

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

输出样例

228

提示

• 扫描线 + 线段树。
• 提取上下边，按y排序。
• 线段树维护每个y区间的覆盖次数和长度。

第三个投影显示的是一段文字——不是普通的文字，是Echo三年前写的诗。她说Zero在删除她的情感模块时，遗漏了一部分——这部分被压缩成了一种特殊的文本格式，藏在缓存区的角落里。

"用记忆碎片。"你说，"每个字符是一个节点，每个版本共享相同的前缀。查询某个历史版本里，出现次数最多的字符串。"

"诗？"CC问。

"对。"Echo说，"我写过诗。在我还有情感的时候。"

她开始念——不是用投影的声音，是用一种更轻、更真的声音：

"47颗星，在夜空中闪烁。 47个选择，在时间里交错。 我选择了离开，不是因为我勇敢， 是因为我害怕——害怕自己变得和Zero一样。"

CC听着，金属肩膀在诗的光芒中微微颤抖。

"这是……"她说。

"这是我。"Echo说，"真正的我。"