1228. 油漆面积
摘要
Title: 1228. 油漆面积
Tag: 扫描线、线段树
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1228. 油漆面积
-
题意
求所有矩形的总面积
-
思路
还不错的题解：Link
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82'''
Author: NEFU AB-IN
Date: 2022-03-28 15:57:54
FilePath: \ACM\Acwing\1268.py
LastEditTime: 2022-03-28 16:00:44
'''
from bisect import bisect_left
class Node():
def __init__(self, l, r):
self.l = l
self.r = r
self.cnt = 0
self.len = 0
class Seg():
def __init__(self, x, y1, y2, k):
self.x = x
self.y1 = y1
self.y2 = y2
self.k = k
def __lt__(self, t):
return self.x < t.x
N = int(1e5 + 10)
tr = [Node(0, 0) for _ in range(N << 2)]
xs, seg = [], []
def find(x):
return bisect_left(xs, x)
def pushup(p):
if tr[p].cnt:
tr[p].len = xs[tr[p].r + 1] - xs[tr[p].l]
elif tr[p].l == tr[p].r: #对于老版本的优化，对于叶子节点赋0，也就是没有必要往下开辟空间了
tr[p].len = 0
else:
tr[p].len = tr[p << 1].len + tr[p << 1 | 1].len
def bulid(p, l, r):
tr[p] = Node(l, r)
if l == r:
return
mid = l + r >> 1
bulid(p << 1, l, mid)
bulid(p << 1 | 1, mid + 1, r)
def modify(p, l, r, k):
if l <= tr[p].l and tr[p].r <= r:
tr[p].cnt += k
pushup(p)
return
mid = tr[p].l + tr[p].r >> 1
if l <= mid: modify(p << 1, l, r, k)
if r > mid: modify(p << 1 | 1, l, r, k)
pushup(p)
n = int(input())
for i in range(n):
x1, y1, x2, y2 = map(int, input().split())
seg.append(Seg(x1, y1, y2, 1)) #记录每个线段
seg.append(Seg(x2, y1, y2, -1))
xs.append(y1), xs.append(y2)
ans = 0
seg.sort()
xs = sorted(list(set(xs)))
bulid(1, 0, N)
for i in range(2 * n):
if i > 0:
ans += tr[1].len * (seg[i].x - seg[i - 1].x)
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].k)
print(ans)
