Python 版题解
题目描述
给定多个矩形的坐标,求并区间的面积
扫描线算法 + 线段树
时间复杂度
$O(log\ n)$
分析
本题采用特殊的 懒标记 方法,即懒标记不下传,没有 pushdown
的过程。这是因为我们查询的是 并区间。
如下图所示,假设第一次进入长度为 6-15
,根据 modify
函数,我们会给区间 6-10
和 11-15
打上标记,并计算对应的区间长度;
假设第二次进入长度为 7-12
,我们会给区间 7
,8
,9-10
,11-12
打上标记。但在计算区间长度时,由于区间 6-10
和 11-15
仍存在标记,因此区间长度仍为 $10$。(这很 make sense,因为长度 1 包含长度 2)
当长度 7-12
出去时,也只是消除了区间 7
,8
,9-10
,11-12
上的标记,不会影响区间 6-10
和 11-15
的标记,因此区间长度还是不变。
其余情况也是类似的分析方式。
总的来说,当大区间打上标记时,小区间如何操作都不会有影响,这很符合并集的思想。
Python 代码
n = int(input())
N = 10010
class Segment():
def __init__(self):
self.x = 0
self.y1 = 0
self.y2 = 0
self.k = 0
# 内置方法,设置比较方式
def __lt__(self, other):
return self.x < other.x
seg = [Segment() for i in range(N*2)]
class Node():
def __init__(self):
self.l = 0
self.r = 0
self.cnt = 0
self.leng = 0
tr = [Node() for i in range(N*4)]
def pushup(u):
if tr[u].cnt > 0: # 存在标记,则直接计算区间长度
tr[u].leng = tr[u].r - tr[u].l + 1
elif tr[u].l == tr[u].r: # 没有标记,且是叶节点,则设长度为 0,避免影响父节点长度计算
tr[u].leng = 0
else: # 没有标记,则计算子节点长度和
tr[u].leng = tr[u<<1].leng + tr[u<<1|1].leng
def build(u, l, r):
tr[u].l, tr[u].r = l, r
if l == r:
return
mid = l + r >> 1
build(u << 1, l, mid)
build(u << 1 | 1, mid + 1, r)
def modify(u, l, r, k):
if tr[u].l >= l and tr[u].r <= r: # 查询区间包含节点区间,则打上标记
tr[u].cnt += k
pushup(u)
else:
mid = tr[u].l + tr[u].r >> 1
if l <= mid:
modify(u<<1, l, r, k)
if r > mid:
modify(u<<1|1, l, r, k)
pushup(u)
m = 0
for i in range(n):
x1, y1, x2, y2 = map(int, input().split())
seg[m].x, seg[m].y1, seg[m].y2, seg[m].k = x1, y1, y2, 1
m += 1
seg[m].x, seg[m].y1, seg[m].y2, seg[m].k = x2, y1, y2, -1
m += 1
seg = sorted(seg[:m])
build(1, 0, 10000)
res = 0
for i in range(m):
if i > 0:
res += tr[1].leng * (seg[i].x - seg[i-1].x)
modify(1, seg[i].y1, seg[i].y2 - 1, seg[i].k)
print(res)
y 总好强, orz orz