题目描述

墙上粘贴了 $n$ 个相同形状的矩形海报。它们的边都是垂直或水平的。每个矩形可以被其他矩形部分或完全覆盖。所有矩形的并集边界的长度称为周长。现在请你编程计算这个周长是多少。

图 1 显示了一个包含 7 个矩形的图形样例，图 2 给出了它的并集边界。

每个矩形的顶点都有一个整数坐标。

输入格式

第一行输入整数 $n$，表示矩形的数量。

接下来 $n$ 行，每行四个整数 $x_1, y_1, x_2, y_2$ 用以描述一个矩形，$(x_1, y_1)$ 为矩形的左下角坐标，$(x_2, y_2)$ 为矩形的右上角坐标。

输出格式

输出一个整数，表示矩形并集的周长。

样例

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

样例解释

矩形坐标

矩形 1: $(-15, 0)$ 到 $(5, 10)$
矩形 2: $(-5, 8)$ 到 $(20, 25)$
矩形 3: $(15, -4)$ 到 $(24, 14)$
矩形 4: $(0, -6)$ 到 $(16, 4)$
矩形 5: $(2, 15)$ 到 $(10, 22)$
矩形 6: $(30, 10)$ 到 $(36, 20)$
矩形 7: $(34, 0)$ 到 $(40, 16)$

并集边界计算

这些矩形的并集形成多个连通区域，总边界长度（周长）为 $228$。
可以通过扫描线算法（水平扫描和垂直扫描）分别计算水平边界和垂直边界的总长度。

计算方法简述：

1. 对 $x$ 方向扫描：计算所有垂直边的贡献。
2. 对 $y$ 方向扫描：计算所有水平边的贡献。
3. 将两部分相加得到总周长。

注意：坐标范围较大（$[-10000, 10000]$），且 $n \le 5000$，需要离散化处理。

数据范围

• $0 \le n < 5000$
• $-10000 \le x_i, y_i \le 10000$

算法标签

扫描线、离散化、线段树

思路提示

由于矩形都是轴对齐的，周长可以分为水平边和垂直边两部分独立计算：

1. 垂直边贡献：对于每个 $x$ 坐标，计算在 $y$ 方向上被覆盖的区间长度变化。当从左到右扫描时，垂直边的长度等于当前扫描线处覆盖区间总长度与上一次覆盖区间总长度之差的绝对值。
2. 水平边贡献：同理，从上到下扫描 $y$ 坐标，计算 $x$ 方向上覆盖区间的变化。

使用线段树维护当前扫描线上被覆盖的区间总长度，并注意处理区间开闭问题（通常采用左闭右开或半开半闭区间）。