1
# Runtime: 133 ms (Top 41.78%) | Memory: 13.9 MB (Top 70.89%)
2
class SegmentTree:
3
    def __init__(self, xs):
4
        # cnts[v] means that the node's interval is active
5
        self.cnts = defaultdict(int)
6
        # total[v] length of active intervals that are contained the node's interval
7
        self.total = defaultdict(int)
8
        self.xs = xs
9

10
    def update(self, v, tl, tr, l, r, h):
11
        # node interval [tl,tr] does not overlap with query interval [l,r]
12
        if r < tl or tr < l:
13
            return
14
        # node interval is included in the query interval
15
        if l <= tl and tr <= r:
16
            self.cnts[v] += h
17
        else:
18
            tm = (tl + tr) // 2
19
            self.update(v * 2, tl, tm, l, r, h)
20
            self.update(v * 2 + 1, tm + 1, tr, l, r, h)
21
        # node interval is included in the active interval
22
        if self.cnts[v] > 0:
23
            self.total[v] = self.xs[tr + 1] - self.xs[tl]
24
        else:
25
            self.total[v] = self.total[v * 2] + self.total[v * 2 + 1]
26
        return self.total[v]
27

28

29
class Solution:
30
    def rectangleArea(self, rectangles):
31
        # index i means the interval from xs[i] to xs[i+1]
32
        xs = sorted(set([x for x1, y1, x2, y2 in rectangles for x in [x1, x2]]))
33
        xs_i = {x: i for i, x in enumerate(xs)}
34
        st = SegmentTree(xs)
35
        L = []
36
        for x1, y1, x2, y2 in rectangles:
37
            L.append([y1, 1, x1, x2])
38
            L.append([y2, -1, x1, x2])
39
        L.sort()
40
        cur_y = cur_x_sum = area = 0
41
        for y, open_close, x1, x2 in L:
42
            area += (y - cur_y) * cur_x_sum
43
            cur_y = y
44
            # one index corresponds to one interval, that's why we use xs_i[x2]-1 instead of xs_i[x2]
45
            st.update(1, 0, len(xs) - 1, xs_i[x1], xs_i[x2] - 1, open_close)
46
            cur_x_sum = st.total[1]
47

48
        return area % (10**9 + 7)