0850 - Rectangle Area II
题干
破题
要求矩形覆盖的面积，在做了天际线问题和完美矩形问题后，这个问题的思路就看得非常清楚了，只需要沿着某一轴扫描，计算在另一轴上覆盖的长度，计算的时机是遇到每个矩形的入边或者出边的（重复的不算），这样拆分成一个个小矩形，就得到了覆盖的面积和。
于是问题的关键，不妨以 $x$ 轴为扫描方向，就在于如何动态地计算 $y$ 轴上的覆盖长度。
由于本题的限制相当宽松，建筑的数量最多只到 $200$ ，因此可以允许其他非最优解的多种复杂度的方法。
解①：
在 $y$ 轴，对每个矩形竖直的边，$[y_1, y_2]$ ，把边的开始位置 $y_1$，标记 $1$ ，它的结束位置标记 $-1$ ，把这些标记按照 $y$ 轴上的坐标进行排序，对这些标记进行累加，最后的和一定是 $0$ ，它的变化过程一定是从 $0$ 到正值再到 $0$ ，每一次归 $0$ 就意味着一条线段的结束，把这些分离的线段累加起来，这就得到了此时的 $y$ 轴上的线段和。
由于每次扫描都需要排序并重新装填 $y$ 坐标，因此总的时间复杂度为 $O(n\cdot (n\text{log}n + n)) = O(n^2\text{log}n)$ 。
这有可以优化的地方，如果提前把 $y$ 轴离散化，就可以直接做坐标-排名的映射，就不需要每次都排序 $y$ 坐标，于是就只剩下装填所有的 $y$ 坐标的成本，时间复杂度就可以降低为 $O(n^2)$ 。
解②：
更直接地，把 $x$ 轴坐标也离散化，与离散化地 $y$ 轴坐标构成二维数组，每个矩形（的 $4$ 个顶点）在这个二维数组上映射，然后扫描这个二维数组计算面积。
时间复杂度是离散化+矩形映射+统计： $O(n\text{log}n + n + n^2)$ = $O(n^2)$
解③：
上述地算法之所以不够优，关键在于每扫描到一个位置，就要用至少 $O(n)$ 的时间复杂度装填 $y$ 坐标，而拿到这道题目后，第一眼可以看出，我们应该可以用前面的分段树或者树状数组来在 $O(\text{log}n)$ 的时间内装填 $y$ 坐标。
这看起来非常简单，但是，但是，在开始写的时候，才发现这道题并不如想象中那么简单，它有别于天际线那道题的关键是建筑都是连续的，不存在从半空中开始涨起，而矩形没有这个性质，它在 $y$ 轴上的排列可能是不连续的。
线段的取消
这样的话似乎只能在 y 轴空间上存储整个线段，但是如何在矩形结束的时候准确撤销它所属的线段呢？ 但是分段树可以按照区间1 额外存储该区间边的数量，这样在新的边加入时，更新的时候把它覆盖的区间的边的数量增 $1$ ，取消边的时候就把区间的边的数量减 $1$ ，在二分区间向下更新的时候，如果某个区间的边数不为零，那么这个区间的值就是它代表的整个线段的长度，否则，就要由子区间的值求和得到。
这样分段树全区间的值，就是 $y$ 轴上线段的总长度。
区间的表示
以为解决了边的添加和取消就完事大吉了吗？，不，还有很大的问题：如果分段树上每个点对应某个坐标，就像习惯得那样，这就面临坐标划分与区间划分二者不一致的问题，对于用坐标表示的边来说，坐标是可重叠的，而分段树的区间划分两端是不可重叠的。举例说，对于 [0, 2] 的边的划分，按照坐标来说就是 $[0, 1]$ 和 $[1, 2]$ ，而按照区间划分则为 $[0,1]$ 和 $[2, 2]$ 。
这实在是不好解决，因为分段树上 $[a, b]$ 的区间不能表示为坐标上 $[a, b]$ 的边，必须寻找一个新的与分段树区间划分一致地表示。于是我们可以考虑坐标可以重叠，但是区间不会重叠，可以定义标号 $i$ 表示坐标从 $[i, i+1]$ 的区间，这样分段树上的 $[a, b]$ 就不再表示坐标 $[a, b]$ 的边，而是标号 $a$~$b$ ，一共 $b-a+1$ 个单位区间的和，这样问题就解决了！
取模与数据类型
最后由于计算结果过大，需要对结果取模，其中模数给得是 $10^9+7$ ，是个质数，这有什么说法吗？
质数取模得可以想到的是中国剩余定理，如果一个一元线性同余2方程的模数两两互质，那么这个方程是有解的而且可以构造出来，但它显然和我们这里没什么关系，事实上可以取任何一个大小符合条件的数，至于质不质地也没什么关系。
至于取模运算本身倒是（对我们有用的）运算性质：
\[\begin{array}{l} &a \cdot b\pmod{N} &\equiv (a\pmod{N} \cdot b\pmod{N})\pmod{N}\\ &(a+b) \pmod{N} &\equiv (a\pmod{N} + b\pmod{N})\pmod{N} \end{array}{}\]另外需要吐槽得是本题 LeetCode 习惯性地给出的 i32 类型就不适当，它在例题上，在对结果取模前就数值溢出了，你必须手动把它提到更大的整数类型上。
统一排序
由于在每个不同坐标的矩形的进入或离开时都要计算面积，因此像之前把入边和出边分开保存排序的做法3会让代码显得很冗余吗，于是直接把 $x$ 坐标、入边出边的类型标记和 $y$ 轴两坐标，构成一个 $4$ 元组，统一排序。
Rust 实现4
分段树
struct SegmentTree {
/// (coverd edges number, range_sum)
data: Vec<(usize, usize)>,
y_end: usize,
y_data: Vec<i32>,
}
/// DFS 型
impl SegmentTree {
fn new(y_data: Vec<i32>, y_end: usize) -> Self {
SegmentTree {
// numbers of interval units
data: vec![(0, 0); (y_end - 1) * 2],
y_end,
y_data,
}
}
fn update(&mut self, l: usize, r: usize, mark: bool) {
self.update_(l, r, 0, self.y_end - 2, 0, mark)
}
fn update_(&mut self, l: usize, r: usize, tl: usize, tr: usize, i: usize, mark: bool) {
if l > r {
return;
}
let mid = (tl + tr) / 2;
let sub_len = (mid - tl) + 1;
let i_lf = i + 1;
let i_rh = i + 2 * sub_len as usize;
if l == tl && r == tr {
if mark {
self.data[i].0 = self.data[i].0 + 1;
}
else {
self.data[i].0 = self.data[i].0 - 1;
}
} else {
self.update_(l, min(mid, r), tl, mid, i_lf, mark);
self.update_(max(mid + 1, l), r, mid + 1, tr, i_rh, mark);
}
if self.data[i].0 > 0 {
self.data[i].1 = (self.y_data[tr + 1] - self.y_data[tl]) as usize;
}
else if tl != tr {
self.data[i].1 = self.data[i_lf].1 + self.data[i_rh].1;
}
else {
self.data[i].1 = 0;
}
}
fn sum(&self) -> i32 {
self.data[0].1 as i32
}
}
其中 y_end 指得是原坐标的排名，加一后的值，表示总共排名的数量或者总的不同 $y$ 坐标的数量。内部构成的区间数应该比总的不同 $y$ 坐标数少一。
完整过程
use std::{
cmp::{max, min},
collections::{BTreeSet, HashMap},
};
const M: u64 = 1_000_000_000 + 7;
pub fn solve(rectangles: Vec<Vec<i32>>) -> i32 {
let (y_data, y_map) = build_y_discrezation(&rectangles);
let lines = build_x_lines(rectangles, &y_map);
let mut tree = SegmentTree::new(y_data, y_map.len());
let mut acc = 0;
let mut x0 = lines[0].0;
for (x, ty, y1, y2) in lines {
if x != x0 {
let h = tree.sum();
acc += ((x - x0) as u64 * h as u64) % M;
x0 = x;
}
tree.update(y1, y2 - 1, ty);
}
(acc as u64 % M) as i32
}
fn build_y_discrezation(rectangles: &Vec<Vec<i32>>) -> (Vec<i32>, HashMap<i32, usize>) {
let mut set = BTreeSet::new();
for rec in rectangles {
set.insert(rec[1]);
set.insert(rec[3]);
}
(
set.iter().cloned().collect(),
set.into_iter()
.enumerate()
.map(|(i, x)| (x, i as usize))
.collect(),
)
}
fn build_x_lines(
rectangles: Vec<Vec<i32>>,
y_map: &HashMap<i32, usize>,
) -> Vec<(i32, bool, usize, usize)> {
let mut lines = Vec::with_capacity(rectangles.len() * 2);
for rec in rectangles {
let x1 = rec[0];
let x2 = rec[2];
let y1 = *y_map.get(&rec[1]).unwrap();
let y2 = *y_map.get(&rec[3]).unwrap();
lines.push((x1, true, y1, y2)); // 0 true for enter
lines.push((x2, false, y1, y2)); // 1 false for exit
}
lines.sort_unstable();
lines
}
注解
