<p>You are given a 2D array of axis-aligned <code>rectangles</code>. Each <code>rectangle[i] = [x<sub>i1</sub>, y<sub>i1</sub>, x<sub>i2</sub>, y<sub>i2</sub>]</code> denotes the <code>i<sup>th</sup></code> rectangle where <code>(x<sub>i1</sub>, y<sub>i1</sub>)</code> are the coordinates of the <strong>bottom-left corner</strong>, and <code>(x<sub>i2</sub>, y<sub>i2</sub>)</code> are the coordinates of the <strong>top-right corner</strong>.</p>

<p>Calculate the <strong>total area</strong> covered by all <code>rectangles</code> in the plane. Any area covered by two or more rectangles should only be counted <strong>once</strong>.</p>

<p>Return <em>the <strong>total area</strong></em>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://s3-lc-upload.s3.amazonaws.com/uploads/2018/06/06/rectangle_area_ii_pic.png" style="width: 600px; height: 450px;" />
<pre>
<strong>Input:</strong> rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
<strong>Output:</strong> 6
<strong>Explanation:</strong> A total area of 6 is covered by all three rectangles, as illustrated in the picture.
From (1,1) to (2,2), the green and red rectangles overlap.
From (1,0) to (2,3), all three rectangles overlap.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> rectangles = [[0,0,1000000000,1000000000]]
<strong>Output:</strong> 49
<strong>Explanation:</strong> The answer is 10<sup>18</sup> modulo (10<sup>9</sup> + 7), which is 49.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= rectangles.length &lt;= 200</code></li>
	<li><code>rectanges[i].length == 4</code></li>
	<li><code>0 &lt;= x<sub>i1</sub>, y<sub>i1</sub>, x<sub>i2</sub>, y<sub>i2</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>x<sub>i1 &lt;= </sub>x<sub>i2</sub></code></li>
	<li><code>y<sub>i1 &lt;=</sub> y<sub>i2</sub></code></li>
</ul>

class SegTree(object):

    def __init__(self, st, ed, X):
        self.start = st
        self.end = ed
        self._left = None
        self._right = None
        self.total = 0
        self.cnt = 0
        self.X = X

    @property
    def mid(self):
        return (self.start + self.end) >> 1

    @property
    def left(self):
        if not self._left:
            self._left = SegTree(self.start, self.mid, self.X)
        return self._left

    @property
    def right(self):
        if not self._right:
            self._right = SegTree(self.mid, self.end, self.X)
        return self._right

    def update(self, st, ed, val):
        if st >= ed:
            return 0

        if st == self.start and ed == self.end:
            self.cnt += val
        else:
            self.left.update(st, min(self.mid, ed), val)
            self.right.update(max(self.mid, st), ed, val)

        if self.cnt > 0:
            self.total = self.X[self.end] - self.X[self.start]
        else:
            self.total = self.right.total + self.left.total

        return self.total


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        """
        Approach 1
        Segment Tree
        """
        # x_set = set()
        # events = []
        # MOD = 10**9 + 7

        # for x1, y1, x2, y2 in rectangles:
        #     if x1 == x2 or y1 == y2:
        #         continue
        #     events.append((y1, 1, x1, x2))
        #     events.append((y2, -1, x1, x2))
        #     x_set.add(x1)
        #     x_set.add(x2)

        # events.sort()
        # x_set = sorted(list(x_set))
        # x_mapping = {v: idx for idx, v in enumerate(x_set)}
        # seg_tree = SegTree(0, len(x_set) - 1, x_set)

        # ans = 0
        # cur_width = 0
        # prev_y = 0
        # for y, v, x1, x2 in events:
        #     ans += cur_width * (y - prev_y)
        #     ans %= MOD
        #     cur_width = seg_tree.update(x_mapping[x1], x_mapping[x2], v)
        #     # print(y, v, x1, x2, cur_width, ans)
        #     prev_y = y

        # return ans

        """
        Approach 2
        Line Sweep
        """
        events = []
        MOD = 10**9 + 7

        for x1, y1, x2, y2 in rectangles:
            if x1 == x2 or y1 == y2:
                continue
            events.append((y1, 1, x1, x2))
            events.append((y2, -1, x1, x2))

        events.sort()
        activities = []
        ans = 0
        pre_y = 0
        for y, v, x1, x2 in events:
            pre_x = -1
            for x11, x22 in activities:
                st = max(x11, pre_x)
                if st < x22:
                    ans += (x22 - st) * (y - pre_y)
                    pre_x = x22
            pre_y = y

            if v == 1:
                activities.append((x1, x2))
                activities.sort()
            else:
                activities.remove((x1, x2))

        return ans % MOD

16700