线段树+扫描线解决矩形面积问题
蓝桥杯2017年省赛最后一题是求重叠矩形面积的题目，这类题目最常用的做法就是用线段树+扫描线来解决。又由于数据给的比较大，所以还需要对数据进行离散化处理。下面分别介绍线段树，扫面线的概念。
预备知识
线段树
线段树是常用来维护 区间信息的数据结构。
线段树可以在$O(logN)$的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。常用于解决矩形面积，矩形周长，区间和（最大最小值）等问题。
下面结合代码详细说明（以区间和为例）：
class SegmentTreeNode: # 树节点
def __init__(self, start, end, val, left=None, right=None):
self.start = start # 区间开始点
self.end = end # 区间结束点
self.sum = val # 区间和 可以替换成最大值等等
self.left = left # 左子树
self.right = right # 右子树
def build_tree(start, end, vals): # 构建线段树
if start == end: # 叶子节点
return SegmentTreeNode(start, end, val[start])
mid = (start+end)//2 # 类似二分思想
# 递归构建左右子树
left = build_tree(start, mid, vals)
right = build_tree(mid+1, end, vals)
# 返回根节点
return SegmentTreeNode(start, end, left.sum+right.sum, left, right)
def update_tree(root, index, val): # 更新index节点的值并更新整棵树
if root.start == index == root.end: # 找到index节点
root.sum = val # 更新节点值
return
mid = (root.start+root.end)//2 # 二分
if index > mid: # index在右子树
update_tree(root.right, index, val) # 递归更新右子树
else: # 在左子树
update_tree(root.left, index, val) # 递归更新左子树
root.sum = root.left.sum+root.right.sum # 更新当前节点
def query_sum(root, i, j): # 区间查询
if root.start == i and root.end == j: # 查询区间等于当前节点区间
return root.sum
mid = (root.start+root.end)//2 # 二分
if i>mid: # 查询区间左端点大于 mid 直接查询右子树
return query_sum(root.right, i, j)
elif j <= mid: # 同理
return query_sum(root.left, i, j)
# 查询区间左端点在左子树，右端点在右子树 分别查询再合并
else return query_sum(root.left, i, mid)+query_sum(root.right, mid+1, j)代码不是很难理解，最主要是mid用的非常秒。mid参数也可以存下来避免每次计算
扫描线
扫描线其实并不是一个具体的数据结构，只是一种思想。利用扫描线，我们可以快速并且无重复的计算出矩形的面积。扫描线结构如下：
class Line:
def __init__(self, x1, x2, height, f):
self.x1 = x1 # 扫描线左端点
self.x2 = x2 # 扫描线右端点
self.height = height # 高度
self.f = f # 1为入边 -1为出边分析
本题思路其实非常清晰，是扫描线+线段树的模板题。
首先将扫描线设定为平行于X轴的方向，将矩形的边都当作扫面线处理并储存起来。
代码
下面给出代码实现并结合代码解释具体细节。
from functools import cmp_to_key
class Line: # 扫面线数据结构
def __init__(self, x1, x2, h, f):
self.x1 = x1 # 线段左端点
self.x2 = x2 # 右端点
self.height = h # 高度
self.f = f # 入边=1 出边=-1
def line_cmp(l1:Line, l2:Line): # 扫描线排序
return l1.height - l2.height
class SegTree: #线段树
def __init__(self, pl, pr):
self.pl = pl # 区间左端点
self.pr = pr # 区间右端点
self.cnt = 0 # 覆盖次数计数
self.l = 0 # 区间长度
self.lson = None # 左子树
self.rson = None # 右子树
N = 10000
X = [0] * (2*N) # 存储N个矩形的2N个顶点
lines = [] # 扫描线数组
def build_tree(pl ,pr): # 构建扫描树（空）
t = SegTree(pl, pr)
if pl == pr:
return t
mid = (pl+pr)//2
t.lson = build_tree(pl, mid)
t.rson = build_tree(mid+1, pr)
return t
def update_length(pTree: SegTree, tl, tr): # 更新当前节点的长度
if pTree.cnt: # 如果被覆盖（入边）
pTree.l = X[tr]-X[tl-1] # 长度为该扫描线的长度
elif tl == tr: # 如果为出边，而且区间左右端点相同
pTree.l = 0 # 长度为0
else: # 为出边而且区间左右端点不同
pTree.l = pTree.lson.l + pTree.rson.l # l为其左右子树的长度之和
def update(tree: SegTree, pl, pr, value): # 更新区间树,pl,pr都是X的索引,value是要更新的值
if not tree:
return
tl = tree.pl # 当前树节点的左端点
tr = tree.pr # 右端点
if pl <= tl and pr >= tr: # 要更新的区间（pl，pr）整好在该节点的范围内 即属于该节点
tree.cnt += value # 更新cnt value是f即出入边 与cnt相加为覆盖次数
update_length(tree, tl, tr) # 更新区间长度
return
m = (tl + tr)//2
if pl <= m: # 更新其左子树
update(tree.lson, pl, pr, value)
if pr > m: # 更新其右子树
update(tree.rson, pl, pr, value)
update_length(tree, tl, tr) # 更新长度
if __name__ == "__main__":
n = int(input())
index = 0 # 扫描线个数计数
ans = 0 # 最终答案
for i in range(n):
tmp = input().split()
x1, y1, x2, y2 = int(tmp[0]), int(tmp[1]), int(tmp[2]), int(tmp[3])
# 每读入一个矩形 添加两条扫描线
X[index] = x1
lines.append(Line(min(x1, x2), max(x1, x2), y1, 1))
index += 1
X[index] = x2
lines.append(Line(min(x1, x2), max(x1, x2), y2, -1))
index += 1
X = X[:index]
X = list(set(X)) # 端点去重
X.sort() # 排序
lines.sort(key=cmp_to_key(line_cmp)) # 扫描线按照高度排序
# x_end = len(set(X))
x_end = len(X) # 去重后的总数量
root = build_tree(1, x_end) # 构建扫描树
for i in range(index-1):
pl = X.index(lines[i].x1) # 从X中找到line[i]的左端点的真正索引（X经过排序被打乱）
pr = X.index(lines[i].x2) # 从X中找到line[i]的右端点
update(root, pl+1, pr, lines[i].f) # 更新区间树
# 用当前扫描线长度*两扫描线高度之差记为当前区域长方形面积
ans += root.l*(lines[i+1].height-lines[i].height)
print(ans)
