0391 - Perfect Rectangle
题干
破题
求一个完美覆盖的矩形，首先想到的就是通过面积比较进行判断，也就是所有矩形的最右、最上、最左、最下4个坐标构成的矩形的面积是否等于各小矩形的面积之和。但是只有面积的比较还不足以证明是“完美覆盖”，因为面积相等还包括空隙和重叠并存的情况，必须要确保小矩形之间没有空隙或者没有覆盖。
在面积相等的情况下，如果小矩形之间有空隙，则必然还存在重叠，反之有重叠必然也有空隙，因此只要能检查任意空隙或者重叠任意一项即可。
解①：扫描线
说到重叠，就可以回到经典的扫描线+分段树/树状数组的解决方案：可以扫描一个维度然后在另一个维度上建树，利用数据结构做区间更新后的区间查询，以观察是否有重叠的边。
比如可以扫描 $x$ 轴，在 $y$ 轴上建树，每扫描到一个小矩形 $[x, y, a, b]$，就把它在 $y$ 轴上的区间 $[y, b]$ 更新到树上，在这个过程中检查 $[y, b]$ 是否完全未被覆盖，如果未完全未覆盖，意思是当前扫描线位置存在重叠的边，直接返回 false；当这个小矩形结束时，再把 $[y, b]$ 的更新取消，就这样扫描到最后一个小矩形，如果都没问题，就说明不存在重叠的情况。
区间闭合性
前面讲对于小矩形 $[x, y, a, b]$ 更新 $y$ 轴上的区间 $[y, b]$ ，但这是不准确的，因为对于完美矩形，小矩形紧挨着的情况是正确的1而不是错误的，因此不能用两端闭合的区间表示，而需要用半闭半开区间，不妨用底部闭合顶部开放的区间2，这样就是更新区间 $[y, b-1]$ 。
同样对于扫描线的 $x$ 轴来说，也需要半闭半开区间来容纳小矩形的边紧挨的情况。
数据离散化和排序
照例，建树的那一轴，这里是 $y$ 轴，其上的数据需要离散化处理，但有点儿意外得是，给定的小矩形列表并没有按照任何一个轴来排序，这是什么用意呢，暗示了什么呢？暂且按下不表，我们这次要手动排序了。
from typing import *
from sortedcontainers import SortedList, SortedSet
class Solution:
def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
return solve(rectangles)
def solve(rectangles: List[List[int]]) -> bool:
y_data = SortedSet()
for _, y, _, b in rectangles:
y_data.add(y)
y_data.add(b)
y_map = { y: i for i, y in enumerate(y_data)}
# ...
$x$ 轴也要排序，在计算小矩形面积之和的遍历过程中顺便进行在线地对矩形的竖边按照 $x$ 坐标排序，理论上应当比完整列表上的排序快，$x$ 坐标分为了小矩形的入边和出边，分别用 ent 和 ex 表示3。
# ... def solve
area_sum = 0
ent = SortedList(key=lambda x: x[0])
ex = SortedList(key=lambda x: x[0])
for x, y, a, b in rectangles:
area_sum += (a-x) * (b-y)
y = y_map[y]
b = y_map[b]
ent.add((x, y, b))
ex.add((a, y, b))
del y_map
# ...
$x$ 轴和 $y$ 轴数据排序后就可以计算大矩形的面积，然后进行面积的比较
# ... def solve
min_x = ent[0][0]
max_a = ex[-1][0]
min_y = y_data[0]
max_b = y_data[-1]
cover_area = (max_a - min_x) * (max_b - min_y)
if area_sum != cover_area:
return False
# ...
解⒈⒈：分段树
分段树的如何赋值来表示一个区间的覆盖，这需要考虑。乍一看，好像只需要一个布尔类型的标记，赋值在对应的区间上就可以了，但是这样不能精确表示区间的覆盖程度，比如如果一个父区间下的某个子区间被覆盖了，那么这个父区间是被覆盖了还是没被覆盖？
于是（在更新的时候）我们使用区间的长度来赋值所覆盖区间，这样递归完成后向上更新父区间，到时候只要检查区间的值是否等于区间长度就可以判断该区间是否完全被覆盖，或者是否等于零，表示区间完全未被覆盖。
通过抛出异常传递区间存在重合的情况。
# ... def solve
segtree = SegmentTree(len(y_data))
j = 0
j_end = len(ex)
for x, y, b in ent:
while j < j_end and ex[j][0] <= x:
segtree.update(ex[j][1], ex[j][2]-1, False)
j += 1
try:
segtree.update(y, b-1, True)
except:
return False
return True
class SegmentTree:
"""DFS型"""
def __init__(self, range_len: int):
self.marked = [0] * range_len * 2
self.root = (0, range_len - 1, 0)
def update(self, l: int, r: int, val: bool):
"""It would raise when try to mark an occupied position"""
self._update(l, r, val, *self.root)
def _update(self, l: int, r: int, val: bool, tl: int, tr: int, i: int):
if l > r:
return
range_len = tr - tl + 1
if l == tl and r == tr:
if val and self.marked[i] > 0:
# can't catch class don't inherrit from BaseException
# however so what we could use except to catch
raise "Occupied"
if val:
self.marked[i] = range_len
else:
self.marked[i] = 0
else:
mid = (tl + tr) // 2
sub_l = (mid - tl + 1)
if val and self.marked[i] == range_len:
raise "Occupied"
self._update(l, min(r, mid), val, tl, mid, i+1)
self._update(max(mid+1, l), r, val, mid+1, tr, i+2*sub_l)
self.marked[i] = self.marked[i+1] + self.marked[i+2*sub_l]
解⒈⒉：树状数组
是对树状数组做区间更新后的区间查询，标记区间就是区间里的每个位置的值加一，区间取消标记就是区间里每个位置的值加负一，于是可以通过查询区间和是否为零来测试区间是否有覆盖的情况。
具体算法的公式这里的有关章节已有详细介绍，就不再赘述。
# ... def solve
cobit = CoBIT(len(y_data))
j = 0
j_end = len(ex)
for x, y, b in ent:
while j < j_end and ex[j][0] <= x:
cobit.update(ex[j][1], ex[j][2]-1, -1)
j += 1
if cobit.query(y, b-1) > 0:
return False
cobit.update(y, b-1, 1)
return True
class CoBIT:
"""Range Update & Range Query"""
def __init__(self, range_len: int) -> None:
self.b1 = [0] * range_len
self.b2 = [0] * range_len
def update(self, l: int, r: int, x: int):
"""range add x for [l, r]"""
CoBIT._add(self.b1, l, x)
CoBIT._add(self.b1, r+1, -x)
CoBIT._add(self.b2, l, (l-1) *x)
CoBIT._add(self.b2, r+1, -r*x)
def query(self, l: int, r: int) -> int:
return self.prefix(r) - self.prefix(l-1)
def prefix(self, i :int) -> int:
return CoBIT._prefix(self.b1, i) * i - CoBIT._prefix(self.b2, i)
@staticmethod
def _add(bit: List[int], i: int, x: int):
while i < len(bit):
bit[i] += x
i += (i+1) & -(i+1)
@staticmethod
def _prefix(bit: List[int], i: int) -> int:
acc = 0
while i >= 0:
acc += bit[i]
i -= (i+1) & -(i+1)
return acc
解②：顶点计数
扫描线思路是常规做法，但是回到前面埋下的伏笔：给出的小矩形列表没有按照任何一个轴的方向排序，实际上存在着不需要扫描线加区间查询的数据结构的更Tricky的做法。
可以通过统计每个点的出现次数，判断是否存在小矩形重叠的情况。
在面积相等情况下，重叠与否的充分必要条件是：如果点位于大矩形的四角，那么它们只能出现 $1$ 次；如果位于边上，只能出现 $2$ 次；如果位于其他位置，也就是大矩形内部，那么只能出现 $2$ 或 $4$ 次。
from typing import *
from collections import Counter
class Solution:
def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
return solve(rectangles)
def solve(rectangles: List[List[int]]) -> bool:
vertexs = Counter()
min_x = float("inf")
min_y = float("inf")
max_a = 0
max_b = 0
area_sum = 0
for x, y, a, b in rectangles:
min_x = min(min_x, x)
min_y = min(min_y, y)
max_a = max(max_a, a)
max_b = max(max_b, b)
vertexs[(x, y)] += 1
vertexs[(a, y)] += 1
vertexs[(x, b)] += 1
vertexs[(a, b)] += 1
area_sum += (a-x) * (b-y)
cover_area = (max_a - min_x) * (max_b - min_y)
if area_sum != cover_area:
return False
for (x0, y0), c in vertexs.items():
if x0 in (min_x, max_a) and y0 in (min_y, max_b):
if c != 1:
return False
elif x0 in (min_x, max_a) or y0 in (min_y, max_b):
if c != 2:
return False
else:
if c not in (2, 4):
return False
return True
这里面 Counter 这个类比较甜，它实际上起到了一个提供默认值的默认数组的功能4。
解③：微积分
可以用曲面积分相关知识简化求解过程，事实上所有计算几何相关的问题总有数学上的解决思路，但由于这并不是我们专注的领域，就不介绍了。
注解
