We are given a list of (axis-aligned) rectangles.  Each rectangle[i] = [x1, y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the ith rectangle.
Find the total area covered by all rectangles in the plane.  Since the answer may be too large, return it modulo 10^9 + 7.

Example 1:
Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: As illustrated in the picture.

Example 2:
Input: [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 = (-7)^2 = 49.

Note:

1 <= rectangles.length <= 200
rectanges[i].length = 4
0 <= rectangles[i][j] <= 10^9
The total area covered by all rectangles will never exceed 2^63 - 1 and thus will fit in a 64-bit signed integer.

Difficulty: interview

Starter code:

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        
        def getArea(width):
            res = 0
            prev_low = 0
            for low, high in intervals:
                low = max(prev_low, low)
                if high > low:
                    res += (high - low)*width
                    prev_low = high
            return res

        MOD = 10**9 + 7
        # convert list of rectangles to events
        events = []
        for x1, y1, x2, y2 in rectangles:
            events.append((x1, 0, y1, y2)) #in
            events.append((x2, 1, y1, y2)) #out
        events.sort(key = lambda x : (x[0], x[1]))
        
        # sweep to calculate area
        intervals = []
        area = 0
        prev_x = 0
        for event in events:
            cur_x, type, low, high = event
            area += getArea(cur_x - prev_x)
            if type == 1:
                intervals.remove((low, high))
            else:
                intervals.append((low, high))
                intervals.sort()   
            prev_x = cur_x
                
        
        return area % MOD

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        mod = 10**9 + 7
        events = []
        for x1, y1, x2, y2 in rectangles:
            events.append([x1, 0, y1, y2])
            events.append([x2, 1, y1, y2])
        events.sort(key=lambda x: (x[0], -x[1]))
        
        def getArea(m):
            area = 0
            prev = float('-inf')
            for l, r in heights:
                prev = max(prev, l)
                area += max(0, (r-prev)) * m
                prev = max(prev, r)
            return area
        
        area = 0
        prev = 0
        heights = []
        for event in events:
            cur, close, y1, y2 = event
            area += getArea(cur-prev)
            if close:
                heights.remove((y1, y2))
            else:
                heights.append((y1, y2))
                heights.sort()
            prev = cur
        return area % mod

class Solution:
#    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        # Populate events
#         OPEN, CLOSE = 0, 1
#         events = []
#         for x1, y1, x2, y2 in rectangles:
#             events.append((y1, OPEN, x1, x2))
#             events.append((y2, CLOSE, x1, x2))
#         events.sort()

#         def query():
#             ans = 0
#             cur = -1
#             for x1, x2 in active:
#                 cur = max(cur, x1)
#                 ans += max(0, x2 - cur)
#                 cur = max(cur, x2)
#             return ans

#         active = []
#         cur_y = events[0][0]
#         ans = 0
#         for y, typ, x1, x2 in events:
#             # For all vertical ground covered, update answer
#             ans += query() * (y - cur_y)

#             # Update active intervals
#             if typ is OPEN:
#                 active.append((x1, x2))
#                 active.sort()
#             else:    
#                 active.remove((x1, x2))

#             cur_y = y

#         return ans % (10**9 + 7)
    
#         OPEN, CLOSE = 0,1
#         events = []
#         for x1, y1, x2, y2 in rectangles:
#             events.append((y1, OPEN, x1, x2))
#             events.append((y2, CLOSE, x1, x2))
        
#         events.sort()
        
#         # total length of the horizontal intervals
#         def query():
#             ans = 0
#             cur = -1
#             for x1, x2 in active:
#                 cur = max(cur, x1)
#                 ans += max(0, x2-cur)
#                 cur = max(cur, x2)
#             return ans
            
#         active = []
#         cur_y = events[0][0]
#         res = 0
#         for y, typ, x1, x2 in events:
#             res += query()*(y - cur_y)
            
#             if typ is OPEN:
#                 active.append((x1, x2))
#                 active.sort()
#             else:
#                 active.remove((x1,x2))
            
#             cur_y = y
            
#         return res % (10**9 + 7)
    def rectangleArea(self, rectangles):
        OPEN, CLOSE = 1, -1
        events = []
        nonlocal X
        X = set()
        for x1, y1, x2, y2 in rectangles:
            events.append((y1, OPEN, x1, x2))
            events.append((y2, CLOSE, x1, x2))
            X.add(x1)
            X.add(x2)
        events.sort()

        X = sorted(X)
        Xi = {x: i for i, x in enumerate(X)}

        active = Node(0, len(X) - 1)
        ans = 0
        cur_x_sum = 0
        cur_y = events[0][0]

        for y, typ, x1, x2 in events:
            ans += cur_x_sum * (y - cur_y)
            cur_x_sum = active.update(Xi[x1], Xi[x2], typ)
            cur_y = y

        return ans % (10**9 + 7)
    
class Node(object):
    def __init__(self, start, end):
        self.start, self.end = start, end
        self.total = self.count = 0
        self._left = self._right = None

    @property
    def mid(self):
        return (self.start + self.end) // 2

    @property
    def left(self):
        self._left = self._left or Node(self.start, self.mid)
        return self._left

    @property
    def right(self):
        self._right = self._right or Node(self.mid, self.end)
        return self._right

    def update(self, i, j, val):
        if i >= j: return 0
        if self.start == i and self.end == j:
            self.count += val
        else:
            self.left.update(i, min(self.mid, j), val)
            self.right.update(max(self.mid, i), j, val)

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

        return self.total


class Node(object):
    def __init__(self, start, end):
        self.start, self.end = start, end
        self.total = self.count = 0
        self._left = self._right = None

    @property
    def mid(self):
        return (self.start + self.end) // 2

    @property
    def left(self):
        self._left = self._left or Node(self.start, self.mid)
        return self._left

    @property
    def right(self):
        self._right = self._right or Node(self.mid, self.end)
        return self._right

    def update(self, i, j, val):
        if i >= j: return 0
        if self.start == i and self.end == j:
            self.count += val
        else:
            self.left.update(i, min(self.mid, j), val)
            self.right.update(max(self.mid, i), j, val)

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

        return self.total

class Solution(object):
    def rectangleArea(self, rectangles):
        OPEN, CLOSE = 1, -1
        events = []
        nonlocal X
        X = set()
        for x1, y1, x2, y2 in rectangles:
            events.append((y1, OPEN, x1, x2))
            events.append((y2, CLOSE, x1, x2))
            X.add(x1)
            X.add(x2)
        events.sort()

        X = sorted(X)
        Xi = {x: i for i, x in enumerate(X)}

        active = Node(0, len(X) - 1)
        ans = 0
        cur_x_sum = 0
        cur_y = events[0][0]

        for y, typ, x1, x2 in events:
            ans += cur_x_sum * (y - cur_y)
            cur_x_sum = active.update(Xi[x1], Xi[x2], typ)
            cur_y = y

        return ans % (10**9 + 7)

class Solution:
    # line-sweep , so hard
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs = sorted(set([x for x1, y1, x2, y2 in rectangles for x in [x1, x2]]))
        x_i = {v: i for i, v in enumerate(xs)}
        print(xs)
        print(x_i)
        count = [0] * len(x_i)
        L = []
        # review, kind of like sweep-line issue
        for x1, y1, x2, y2 in rectangles:
            L.append([y1, x1, x2, 1])
            L.append([y2, x1, x2, -1])
        L.sort()
        # print(L)
        cur_y = cur_x_sum = area = 0
        for y, x1, x2, sig in L:
            area += (y - cur_y) * cur_x_sum
            cur_y = y
            for i in range(x_i[x1], x_i[x2]):
                count[i] += sig
            # print(\"zip\")
            # print(count)
            # for x1, x2, c in zip(xs, xs[1:], count):
            # print(x1,x2,c)
            cur_x_sum = sum(x2 - x1 if c else 0 for x1, x2, c in zip(xs, xs[1:], count))
        return area % (10 ** 9 + 7)

    # heap
    # similiar: skyline-problem-218
    def rectangleArea(self, recs):
        \"\"\"
        :type rectangles: List[List[int]]
        :rtype: int
        \"\"\"
        x = set()
        pq = []
        for rec in recs:
            x.add(rec[0])
            x.add(rec[2])
            heapq.heappush(pq, (rec[1], rec[0], rec[2], 1))
            heapq.heappush(pq, (rec[3], rec[0], rec[2], -1))

        x = sorted(list(x))
        xi = {v: i for i, v in enumerate(x)}
        count = [0] * len(x)

        res = 0
        last_l =  pq[0][0]

        while pq:
            cur_l = pq[0][0]

            for i in range(len(x)):
                if count[i] > 0:
                    res += (x[i + 1] - x[i]) * (cur_l - last_l)
                    res = res % (10 ** 9 + 7)

            while pq and pq[0][0] == cur_l:
                cur_l, x1, x2, bound = heapq.heappop(pq)
                for i in range(xi[x1], xi[x2]):
                    count[i] += bound

            last_l = cur_l
        return res



class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        Xs = [x for x1, _, x2, _ in rectangles for x in [x1, x2]]
        Xs.sort()
        X_idx_lookup = {x: idx for idx, x in enumerate(Xs)}
        
        res = 0
        prev_y = 0
        X_span = 0
        
        Ys = [e for x1, y1, x2, y2 in rectangles for e in [[y1, x1, x2, 1], [y2, x1, x2, -1]]]
        Ys.sort()
        
        overlap_count = [0] * len(Xs)
        
        for y, xl, xr, inout in Ys:
            res += (y - prev_y) * X_span
            prev_y = y
            start_idx, end_idx = X_idx_lookup[xl], X_idx_lookup[xr]
            for i in range(start_idx, end_idx):
                overlap_count[i] += inout
            X_span = sum(x2 - x1 if c > 0 else 0 for x1, x2, c in zip(Xs, Xs[1:], overlap_count))
        return res % 1000000007

    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        Xs = [x for x1, _, x2, _ in rectangles for x in [x1, x2]]
        Xs.sort()
        covered = [0] * len(Xs)
        res = 0
        
        keypoints = [e for x1, y1, x2, y2 in rectangles for e in [[y1, x1, x2, 1], [y2, x1, x2, -1]]]
        keypoints.sort()
        
        prev_y = 0
        width_span = 0
        for y, x1, x2, inout in keypoints:
            res += (y - prev_y) * width_span
            prev_y = y
            for i in range(len(covered) - 1):
                a, b = Xs[i], Xs[i + 1]
                if x1 <= a and b <= x2:
                    covered[i] += inout
            width_span = sum(Xs[i + 1] - Xs[i] if covered[i] > 0 else 0 for i in range(len(covered) - 1))
        return res % 1000000007

class Solution(object):
    def rectangleArea(self,rectangles):
        events = []
        MOD = 10**9 + 7
        INT_MIN = -2 **32
        for x1, y1, x2, y2 in rectangles:
            events.append([x1, 0, y1, y2])
            events.append([x2, 1, y1, y2])
        events.sort()

        def merge_intervals(m,intervals):
            l = 0 
            n = len(intervals)
            if n == 0:
                return 0 
            prev = intervals[0]
            l = prev[1]-prev[0]
            print (intervals,l,m)
            prev_end = prev[1]
            for s,t in intervals[1:]:
                if s>=prev_end:
                    l += t-s
                else:
                    if t > prev_end:
                        l = l + (t-s) - (prev_end-s)
                prev_end = max(t,prev_end) 
            return l*m
                
        def gain_area(m):
            area = 0
            prev = INT_MIN
            for l, r in open_intervals:
                prev = max(prev, l)
                area += max(0, (r - prev))
                prev = max(r, prev)
            print (\"gain area\",area,open_intervals)
            return area*m
        
        area = 0
        prev = INT_MIN
        open_intervals = []
        for event in events:
            curr,close,y1,y2 = event
            print (curr,prev,curr-prev)
            area += merge_intervals(curr-prev,open_intervals)
            gain_area(curr-prev)
            if close:
                open_intervals.remove((y1,y2))
            else:
                open_intervals.append((y1,y2))
                open_intervals.sort()
            prev = curr
        return area  % MOD

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        START = 1
        END = 0
        # we want it to end first then start
        MOD = 10**9 + 7
        xaxis = []
        
        for x1, y1, x2, y2 in rectangles:
            xaxis.append((x1, START, y1, y2))
            xaxis.append((x2, END, y1, y2))
        
        xaxis.sort()
        
        prev = 0
        area = 0
        yaxis = []
        for i in range(len(xaxis)):
            x, status, y1, y2 = xaxis[i]
            if i > 0:
                area += self.get_length(yaxis) * (x - prev)
                area %= MOD
            if status == START:
                yaxis.append((y1, y2))
                yaxis.sort()
            else:
                yaxis.remove((y1, y2))
            prev = x
        return area
    
    def get_length(self, yaxis):
        length = 0
        i = 0
        
        prev = (float('-inf'), float('-inf'))
        
        for i in range(len(yaxis)):
            if not self.has_overlap(prev, yaxis[i]):
                length += yaxis[i][1] - yaxis[i][0]
            else:
                if prev[1] >= yaxis[i][1]:
                    continue
                length += yaxis[i][1] - prev[1]
            prev = yaxis[i]
        return length
    
    
    def has_overlap(self, prev, cur):
        if prev[1] < cur[0] or cur[1] < prev[0]:
            return False
        return True
    
    def get_overlap_length(self, prev, cur):
        return min(prev[1], cur[1]) - max(prev[0], cur[0])
        
    
        


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        START = 1
        END = 0
        # we want it to end first then start
        MOD = 10**9 + 7
        xaxis = []
        
        for x1, y1, x2, y2 in rectangles:
            xaxis.append((x1, START, y1, y2))
            xaxis.append((x2, END, y1, y2))
        
        xaxis.sort()
        
        prev = 0
        area = 0
        yaxis = []
        for i in range(len(xaxis)):
            x, status, y1, y2 = xaxis[i]
            if i > 0:
                area += self.get_length(yaxis) * (x - prev)
                area %= MOD
            if status == START:
                yaxis.append((y1, y2))
                yaxis.sort()
            else:
                yaxis.remove((y1, y2))
            prev = x
        return area
    
    def get_length(self, yaxis):
        length = 0
        i = 0
        
        prev = (float('-inf'), float('-inf'))
        
        for i in range(len(yaxis)):
            if not self.has_overlap(prev, yaxis[i]):
                length += yaxis[i][1] - yaxis[i][0]
            else:
                if prev[1] >= yaxis[i][1]:
                    # don't want to update prev end point
                    continue
                length += max(0, yaxis[i][1] - prev[1])
            prev = yaxis[i]
        return length
    
    
    def has_overlap(self, prev, cur):
        if prev[1] < cur[0] or cur[1] < prev[0]:
            return False
        return True
        
    
        


# This is a really difficult problem, method is called line sweeping, it also has interval merge in it
# 1. Time complexity O(N*N*log(N)), space complexity O(N)
# 2. Idea is to use a vertical line to sweep from left to right and accumulate the area by delta x times the total interval length at the x position
# class Solution(object):
#     def rectangleArea(self, rectangles):
#         M=10**9+7
#         events=[]
#         for x1,y1,x2,y2 in rectangles:           
#             events.append((x1,y1,y2,0))
#             events.append((x2,y1,y2,1))
#         events.sort(key=lambda x:x[0])
#         res=0
#         prev=events[0][0]
#         actives=[]
#         def getWidth(actives):
#             actives.sort(key=lambda x:x[0])
#             width=0
#             right=0
#             for active in actives:
#                 width+=max(0,active[1]-max(right,active[0]))
#                 right=max(right,active[1])
#             return width
#         for event in events:
#             if event[0]!=prev:      
#                 res+=getWidth(actives)*(event[0]-prev)
#                 res=res%M
#                 prev=event[0]
#             if not event[3]:
#                 actives.append(event[1:-1])
#             else:
#                 actives.remove(event[1:-1])
#         return res

# This second solution is a practice of segmentation tree, the concept is simpmle but implementation is very challenging, with segmentation tree, each update take log(N) time so time complexity of the enti

class Tree:
    def __init__(self,l,r):
        self.total=0
        self.count=0
        self.l=l
        self.r=r
        self.m=int((self.l+self.r)/2)
        self.isLeaf=True if self.r-self.l==1 else False
        self.left=None if self.isLeaf else Tree(self.l,self.m)
        self.right=None if self.isLeaf else Tree(self.m,self.r)

    def update(self,l,r,count):
        if l>=self.r or r<=self.l:
            return
        if self.isLeaf:
            self.count+=count
            self.total=nums[self.r]-nums[self.l] if self.count else 0
        else:
            self.left.update(l,r,count)
            self.right.update(l,r,count)
            self.total=self.left.total+self.right.total
            
class Solution(object):    
    def rectangleArea(self, rectangles):
        M=10**9+7
        events=[]
        nonlocal nums
        nums=set()
        for x1,y1,x2,y2 in rectangles:           
            events.append((x1,y1,y2,1))
            events.append((x2,y1,y2,-1))
            nums.add(y1)
            nums.add(y2)
        nums=list(nums)
        nums.sort()
        nToI=dict([(n,i) for i,n in enumerate(nums)])
        iTree=Tree(0,len(nums)-1)
        events.sort(key=lambda x:x[0])
        res=0
        prev=events[0][0]
        for event in events:
            if event[0]!=prev:      
                res+=iTree.total*(event[0]-prev)
                res=res%M
                prev=event[0]
            iTree.update(nToI[event[1]],nToI[event[2]],event[3])
        return res



class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        rects = []
        for x1, y1, x2, y2 in rectangles:
            self.helper(rects, 0, x1, y1, x2, y2)
        
        ans = 0
        mod = pow(10, 9) + 7
        for x1, y1, x2, y2 in rects:
            ans += ((x2 - x1) * (y2 - y1)) % mod
        return ans % mod

    def helper(self, rects, index, x1, y1, x2, y2):
        if index == len(rects):
            rects.append([x1, y1, x2, y2])
            return
        
        i1, j1, i2, j2 = rects[index]
        if i1 >= x2 or i2 <= x1 or j1 >= y2 or j2 <= y1:
            self.helper(rects, index + 1, x1, y1, x2, y2)  
            return
        
        if x1 < i1:
            self.helper(rects, index + 1, x1, y1, min(i1, x2), y2)
        
        if x2 > i2:
            self.helper(rects, index + 1, max(i2, x1), y1, x2, y2)
        
        if y1 < j1:
            self.helper(rects, index + 1, max(x1, i1), y1, min(x2, i2), j1)
        
        if y2 > j2:
            self.helper(rects, index + 1, max(x1, i1), j2, min(x2, i2), y2)

# This is a really difficult problem, method is called line sweeping, it also has interval merge in it
# 1. Time complexity O(N*N*log(N)), space complexity O(N)
# 2. Idea is to use a vertical line to sweep from left to right and accumulate the area by delta x times the total interval length at the x position
# class Solution(object):
#     def rectangleArea(self, rectangles):
#         M=10**9+7
#         events=[]
#         for x1,y1,x2,y2 in rectangles:           
#             events.append((x1,y1,y2,0))
#             events.append((x2,y1,y2,1))
#         events.sort(key=lambda x:x[0])
#         res=0
#         prev=events[0][0]
#         actives=[]
#         def getWidth(actives):
#             actives.sort(key=lambda x:x[0])
#             width=0
#             right=0
#             for active in actives:
#                 width+=max(0,active[1]-max(right,active[0]))
#                 right=max(right,active[1])
#             return width
#         for event in events:
#             if event[0]!=prev:      
#                 res+=getWidth(actives)*(event[0]-prev)
#                 res=res%M
#                 prev=event[0]
#             if not event[3]:
#                 actives.append(event[1:-1])
#             else:
#                 actives.remove(event[1:-1])
#         return res

class Tree:
    def __init__(self,l,r):
        self.total=0
        self.count=0
        self.l=l
        self.r=r
        self.m=int((self.l+self.r)/2)
        self.isLeaf=True if self.r-self.l==1 else False
        self.left=None if self.isLeaf else Tree(self.l,self.m)
        self.right=None if self.isLeaf else Tree(self.m,self.r)

    def update(self,l,r,count):
        if l>=self.r or r<=self.l:
            return
        if self.isLeaf:
            self.count+=count
            self.total=nums[self.r]-nums[self.l] if self.count else 0
        else:
            self.left.update(l,r,count)
            self.right.update(l,r,count)
            self.total=self.left.total+self.right.total
            
class Solution(object):    
    def rectangleArea(self, rectangles):
        M=10**9+7
        events=[]
        nonlocal nums
        nums=set()
        for x1,y1,x2,y2 in rectangles:           
            events.append((x1,y1,y2,1))
            events.append((x2,y1,y2,-1))
            nums.add(y1)
            nums.add(y2)
        nums=list(nums)
        nums.sort()
        nToI=dict([(n,i) for i,n in enumerate(nums)])
        iTree=Tree(0,len(nums)-1)
        events.sort(key=lambda x:x[0])
        res=0
        prev=events[0][0]
        for event in events:
            if event[0]!=prev:      
                res+=iTree.total*(event[0]-prev)
                res=res%M
                prev=event[0]
            iTree.update(nToI[event[1]],nToI[event[2]],event[3])
        return res



MOD = 10 ** 9 + 7

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:

        allY = []
        for x1, y1, x2, y2 in rectangles:
            allY.append((y1, 0, x1, x2))
            allY.append((y2, 1, x1, x2))
        allY.sort()

        allX, ans = [], 0
        curHeight = allY[0][0]

        for y, t, x1, x2 in allY:
            ans += self.getX(allX) * (y - curHeight)
            ans %= MOD
            if t == 0:
                bisect.insort(allX, (x1, x2))
            else:
                idx = bisect.bisect_left(allX, (x1, x2))
                #print(idx, x1, x2, allX)
                allX.pop(idx)
                #allX.remove((x1, x2))

            curHeight = y

        return ans

    def getX(self, allX):
        ans = 0
        cur = -1
        for x1, x2 in allX:
            cur = max(cur, x1)
            ans += max(0, x2 - cur)
            cur = max(cur, x2)
        return ans

class Solution:
    def rectangleArea(self, rects: List[List[int]]) -> int:
        xs = sorted(set([x for x1, y1, x2, y2 in rects for x in [x1, x2]]))
        xi = {v: i for i, v in enumerate(xs)}
        cnt = [0] * len(xs)
        L = []
        for x1, y1, x2, y2 in rects:
            L.append([y1, x1, x2, 1])
            L.append([y2, x1, x2, -1])
        L.sort()
        res = last_y = sum_x = 0
        for y, x1, x2, sig in L:
            res += (y-last_y) * sum_x
            last_y = y
            for i in range(xi[x1], xi[x2]):
                cnt[i] += sig
            sum_x = sum(x2-x1 for x1, x2, c in zip(xs, xs[1:], cnt) if c)
        return res %(10**9+7)



class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs = sorted(list(set(x for x1, y1, x2, y2 in rectangles for x in [x1, x2])))
        xs_i = {x: i for i, x in enumerate(xs)}
        
        rects = []
        for x1, y1, x2, y2 in rectangles:
            rects.append((y1, x1, x2, 1))
            rects.append((y2, x1, x2, -1))
        rects = sorted(rects)
        counts = [0] * len(xs_i)
    
        curr_y = 0
        area = 0
        L = 0
        for y, x1, x2, sig in rects:
            area += (y - curr_y) * L
            curr_y = y
            for x in range(xs_i[x1], xs_i[x2]):
                counts[x] += sig
            L = sum(x2 - x1 for x1, x2, s1 in zip(xs, xs[1:], counts) if s1 > 0 )
        return area % (10**9 + 7)

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        # the key point of this solution is how do we generate a list of rectangles that don't overlap with each other. The idea is that we try to add each new rectangle into the list. If it has overlap with existing rectangles, then we break it into muliple parts that don't have overlap with existing rectangles.
        all_rectangles = []
        for rectangle in rectangles:
            self.add_rectangle(all_rectangles, rectangle, 0)
        
        ans = 0
        mod = pow(10, 9) + 7
        for rect in all_rectangles:
            x1, y1, x2, y2 = rect
            ans += ((x2 - x1) * (y2 - y1)) % mod
        
        return ans % mod
    
    def add_rectangle(self, all_rectangles, cur, start):
        if start >= len(all_rectangles):
            all_rectangles.append(cur)
            return
        
        x1, y1, x2, y2 = cur
        rx1, ry1, rx2, ry2 = all_rectangles[start]
        
        if x2 <= rx1 or x1 >= rx2 or y2 <= ry1 or y1 >= ry2:
            self.add_rectangle(all_rectangles, cur, start + 1)
            return
        
        if x1 < rx1:
            self.add_rectangle(all_rectangles, [x1, y1, rx1, y2], start + 1)
        
        if x2 > rx2:
            self.add_rectangle(all_rectangles, [rx2, y1, x2, y2], start + 1)
        
        if y1 < ry1:
            self.add_rectangle(all_rectangles, [max(x1, rx1), y1, min(x2, rx2), ry1], start + 1)
        
        if y2 > ry2:
            self.add_rectangle(all_rectangles, [max(x1, rx1), ry2, min(x2, rx2), y2], start + 1)


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xTicks = set()
        yTicks = set()
        for x1, y1, x2, y2 in rectangles:
            xTicks.add(x1)
            xTicks.add(x2)
            yTicks.add(y1)
            yTicks.add(y2)
        xTicksList = sorted(list(xTicks))
        yTicksList = sorted(list(yTicks))
        
        xTicksDict = {xLable: xi for xi, xLable in enumerate(xTicksList)}
        yTicksDict = {yLable: yi for yi, yLable in enumerate(yTicksList)}
        
        iMax = len(xTicksList)
        jMax = len(yTicksList)
        
        grid = [[0  for j in range(jMax)] for i in range(iMax)]
        ans = 0
        
        for x1, y1, x2, y2 in rectangles:
            for i in range(xTicksDict[x1], xTicksDict[x2]):
                xSide = xTicksList[i+1] - xTicksList[i]
                for j in range(yTicksDict[y1], yTicksDict[y2]):
                    if grid[i][j] == 0:
                        ans += xSide * (yTicksList[j+1]-yTicksList[j])
                        grid[i][j] = 1
        # print(grid)
        return ans%(10**9+7)


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        N = len(rectangles)
        Xvals, Yvals = set(), set()
        for x1, y1, x2, y2 in rectangles:
            Xvals.add(x1); Xvals.add(x2)
            Yvals.add(y1); Yvals.add(y2)

        imapx = sorted(Xvals)
        imapy = sorted(Yvals)
        mapx = {x: i for i, x in enumerate(imapx)}
        mapy = {y: i for i, y in enumerate(imapy)}

        grid = [[0] * len(imapy) for _ in imapx]
        for x1, y1, x2, y2 in rectangles:
            for x in range(mapx[x1], mapx[x2]):
                for y in range(mapy[y1], mapy[y2]):
                    grid[x][y] = 1

        ans = 0
        for x, row in enumerate(grid):
            for y, val in enumerate(row):
                if val:
                    ans += (imapx[x+1] - imapx[x]) * (imapy[y+1] - imapy[y])
        return ans % (10**9 + 7)

from collections import defaultdict
class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        def merge_intervals(intervals):
            if not intervals:
                return 0
            
            intervals.sort()
            end = intervals[0][1]
            width = end - intervals[0][0]
            
            for left, right in intervals:
                if left < end < right:
                    width += right - end
                    end = right
                elif left >= end:
                    width += right - left
                    end = right  
            return width
        
        events = defaultdict(list)
        for x1, y1, x2, y2 in rectangles:
            events[y1].append((1, x1, x2))
            events[y2].append((0, x1, x2))
        
        events = sorted(events.items(), key=lambda x: x[0])
        intervals = []
        area = width = 0
        MOD = 10 ** 9 + 7
        last_y = events[0][0]
        
        for y, event in events:
            area += (y - last_y) * width
            area %= MOD
            
            for flag, x1, x2 in event:
                if flag:
                    intervals.append((x1, x2))
                else:
                    intervals.remove((x1, x2))
            width = merge_intervals(intervals)
            last_y = y
        
        return area

from functools import reduce
class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        def intersection(a, b):
            return [max(a[0], b[0]), max(a[1], b[1]), min(a[2], b[2]), min(a[3], b[3])]
        
        def area(rec):
            dx = max(0, rec[2] - rec[0])  # <================== need to use max!!!
            dy = max(0, rec[3] - rec[1])
            return dx * dy
        
        import itertools
        a = 0
        for i in range(1, len(rectangles) + 1):
            sign = (-1) ** (i + 1)
            for k in itertools.combinations(rectangles, i):
                a += sign * area(reduce(intersection, k))

        return a % (10**9 + 7)
    
    #50
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        
        xmap = [{}, {}]
        xs = [[], []]

        for i in rectangles:
            xs[0].append(i[0])
            xs[0].append(i[2])
            xs[1].append(i[1])
            xs[1].append(i[3])
        xs[0].sort()
        xs[1].sort()
        # print(xs)
        rmap = [[], []]
        for k in range(2):
            cnt = 0
            for i in xs[k]:
                if i not in xmap[k]:
                    xmap[k][i] = cnt
                    rmap[k].append(i)
                    cnt += 1
        # print(rmap)
        grid = [[0] * len(rmap[0]) for _ in range(len(rmap[1]))]  # donnot add extra []

        for r in rectangles:
            for i in range(xmap[0][r[0]], xmap[0][r[2]]):
                for j in range(xmap[1][r[1]], xmap[1][r[3]]):
                    # print(i, j, len(grid), len(grid[0]))
                    grid[j][i] = 1   # <========================= not [i][j]
        
        area = 0
        for i in range(len(rmap[0]) - 1):
            width = rmap[0][i + 1] - rmap[0][i]
            for j in range(len(rmap[1]) - 1):
                if grid[j][i]:
                    area += width * (rmap[1][j + 1] - rmap[1][j])
        return area % (10**9 + 7)
            
        
                
        



import numpy as np
class Solution:
    def rectangleArea(self, A: List[List[int]]) -> int:
        sa = sorted(set(a for x1, y1, x2, y2 in A for a in [x1, x2]))
        xs = sorted(sa)
        dic = {v : i for i, v in enumerate(xs)}
        B = []
        for x1, y1, x2, y2 in A:
            B.append([y1, x1, x2, 1])
            B.append([y2, x1, x2, -1])
        B.sort()
        sum_x = ret = cur_y = 0
        ct = np.zeros(len(xs))
        for y, x1, x2, flag in B:
            ret += sum_x * (y - cur_y)
            cur_y = y
            ct[dic[x1]:dic[x2]] += flag
            sum_x = sum([x2 - x1 for x1, x2, f in zip(xs, xs[1:], ct) if f])
        return ret % (10 ** 9 + 7)

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        all_x, all_y = set(), set()
        for x1, y1, x2, y2 in rectangles:
            all_x.add(x1)
            all_x.add(x2)
            all_y.add(y1)
            all_y.add(y2)
        all_x = list(all_x)
        all_x.sort()
        all_y = list(all_y)
        all_y.sort()
        
        x_map = {val: i for i, val in enumerate(all_x)}
        y_map = {val: i for i, val in enumerate(all_y)}
        area = [[0 for _ in range(len(y_map))] for _ in range(len(x_map))]
        
        for x1, y1, x2, y2 in rectangles:
            for x in range(x_map[x1], x_map[x2]):
                for y in range(y_map[y1], y_map[y2]):
                    area[x][y] = 1
        
        ans = 0
        for x in range(len(x_map)):
            for y in range(len(y_map)):
                if area[x][y]:
                    ans += (all_x[x+1] - all_x[x]) * (all_y[y+1] - all_y[y])
                    if ans > 1000000007:
                        ans %= 1000000007
        return ans

from heapq import heappush, heappop
class Solution(object):
    def rectangleArea(self, recs):
        \"\"\"
        :type rectangles: List[List[int]]
        :rtype: int
        \"\"\"
        x = set()
        pq = []
        for rec in recs:
            x.add(rec[0])
            x.add(rec[2])
            heappush(pq, (rec[1], rec[0], rec[2], 1))
            heappush(pq, (rec[3], rec[0], rec[2], -1))
        
        x = sorted(list(x))
        xi = {v:i for i,v in enumerate(x)}
        count = [0] * len(x)
        
        res = 0
        last_l = cur_l = pq[0][0]
        
#         print(pq)
        
        while pq:
#             print(pq)
#             print(count)
            cur_l = pq[0][0]

            for i in range(len(x)):
                if count[i] > 0:
                    res += (x[i+1] - x[i]) * (cur_l-last_l)
                    res = res % (10**9 + 7)
            while pq and pq[0][0] == cur_l:
#                 print(cur_l, pq)
                cur_l, x1, x2, bound = heappop(pq)
                for i in range(xi[x1],xi[x2]):
                    count[i] += bound
            
            last_l = cur_l
        return res

class Solution(object):
    def rectangleArea(self, rectangles):
        # Populate events
        OPEN, CLOSE = 0, 1
        events = []
        for x1, y1, x2, y2 in rectangles:
            events.append((y1, OPEN, x1, x2))
            events.append((y2, CLOSE, x1, x2))
        events.sort()

        def query():
            ans = 0
            cur = -1
            for x1, x2 in active:
                cur = max(cur, x1)
                ans += max(0, x2 - cur)
                cur = max(cur, x2)
            return ans

        active = []
        cur_y = events[0][0]
        ans = 0
        for y, typ, x1, x2 in events:
            # For all vertical ground covered, update answer
            ans += query() * (y - cur_y)

            # Update active intervals
            if typ is OPEN:
                active.append((x1, x2))
                active.sort()
            else:    
                active.remove((x1, x2))

            cur_y = y

        return ans % (10**9 + 7)

MOD = 10 ** 9 + 7

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:

        allY = []
        for x1, y1, x2, y2 in rectangles:
            allY.append((y1, 0, x1, x2))
            allY.append((y2, 1, x1, x2))
        allY.sort()

        allX, ans = [], 0
        curHeight = allY[0][0]

        for y, t, x1, x2 in allY:
            ans += self.getX(allX) * (y - curHeight)
            ans %= MOD
            if t == 0:
                bisect.insort(allX, (x1, x2))
            else:
                allX.remove((x1, x2))

            curHeight = y

        return ans

    def getX(self, allX):
        ans = 0
        cur = -1
        for x1, x2 in allX:
            cur = max(cur, x1)
            ans += max(0, x2 - cur)
            cur = max(cur, x2)
        return ans

from typing import List


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs = sorted(set([x for x1, y1, x2, y2 in rectangles for x in [x1, x2]]))
        xi = {v: i for i, v in enumerate(xs)}
        co = [0] * len(xs)
        ar = []
        for x1, y1, x2, y2 in rectangles:
            ar.append([y1, x1, x2, 1])
            ar.append([y2, x1, x2, -1])
        ar.sort()

        ly = lx = res = 0

        for y, x1, x2, sig in ar:
            res += (y - ly) * lx
            ly = y

            for i in range(xi[x1], xi[x2]):
                co[i] += sig
            lx = sum(xs[i + 1] - xs[i] if co[i] else 0 for i in range(len(xs) - 1))
        return res % (10 ** 9 + 7)

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs = sorted({x for x1, _, x2, _ in rectangles for x in [x1, x2]})
        index = {v : i for i, v in enumerate(xs)}
        cnt = [0] * len(index)
        events = []
        for x1, y1, x2, y2 in rectangles:
            events.append([y1, x1, x2, 1])
            events.append([y2, x1, x2, -1])
        events.sort()
        curr_y = curr_x_sum = area = 0
        for y, x1, x2, sign in events:
            area += (y - curr_y) * curr_x_sum
            curr_y = y
            for i in range(index[x1], index[x2]):
                cnt[i] += sign
            curr_x_sum = sum(x2 - x1 if c else 0 for x1, x2, c in zip(xs, xs[1:], cnt))
        return area % (10**9 + 7)

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        xs = sorted(set([x for x1, y1, x2, y2 in rectangles for x in [x1, x2]]))
        x_i = {v: i for i, v in enumerate(xs)}
        count = [0] * len(x_i)
        L = []
        for x1, y1, x2, y2 in rectangles:
            L.append([y1, x1, x2, 1])
            L.append([y2, x1, x2, -1])
        L.sort()
        cur_y = cur_x_sum = area = 0
        for y, x1, x2, sig in L:
            area += (y - cur_y) * cur_x_sum
            cur_y = y
            for i in range(x_i[x1], x_i[x2]):
                count[i] += sig
            cur_x_sum = sum(x2 - x1 if c else 0 for x1, x2, c in zip(xs, xs[1:], count))
        return area % (10 ** 9 + 7)

class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        # coord compression
        xs = sorted(set(x for x1, _, x2, _ in rectangles for x in [x1, x2]))
        xi = {v:i for i, v in enumerate(xs)}
        count = [0]*len(xs)
        lines = []
        
        for x1,y1,x2,y2 in rectangles:
            lines.append((y1, x1, x2, 1))
            lines.append((y2, x1, x2, -1))
        lines.sort()
        curr_y, x_sum, res = 0,0,0
        for y, x1, x2, sign in lines:
            res += x_sum*(y-curr_y)
            curr_y = y
            for i in range(xi[x1], xi[x2]):
                count[i] += sign
                
            x_sum = 0
            for i in range(len(xs)-1):
                if count[i]>0:
                    x_sum += xs[i+1]-xs[i]
                    
        return res%(10**9+7)
        


class Solution:
    def rectangleArea(self, rectangles: List[List[int]]) -> int:
        x_set = set()
        points = []
        
        for x1, y1, x2, y2 in rectangles:
            x_set.add(x1)
            x_set.add(x2)
            heapq.heappush(points, (y1, x1, x2, 1))
            heapq.heappush(points, (y2, x1, x2, -1))
        
        x_list = sorted(list(x_set))
        mapping = {x: i for i, x in enumerate(x_list)}
        count = [0]*len(x_list)
        
        res = 0
        pre_y = points[0][0]
        
        while points:
            cur_y = points[0][0]
            h = cur_y-pre_y
            for i in range(len(x_list)-1):
                if count[i] > 0:
                    res += (x_list[i+1]-x_list[i])*h
            res %= (10**9+7)
            
            while points and points[0][0] == cur_y:
                cur_y, x1, x2, cnt = heapq.heappop(points)
                for i in range(mapping[x1], mapping[x2]):
                    count[i] += cnt
            
            pre_y = cur_y
        
        return res