You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: rectangles = [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
Output: 6
Explanation: 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.


Example 2:

Input: rectangles = [[0,0,1000000000,1000000000]]
Output: 49
Explanation: The answer is 1018 modulo (109 + 7), which is 49.


&nbsp;
Constraints:


	1 &lt;= rectangles.length &lt;= 200
	rectanges[i].length == 4
	0 &lt;= xi1, yi1, xi2, yi2 &lt;= 109


class SegmentTree:
    def __init__(self, xs):
        #cnts[v] means that the node's interval is active
        self.cnts = defaultdict(int)
        #total[v] length of active intervals that are contained the node's interval
        self.total = defaultdict(int)
        self.xs = xs

    def update(self, v, tl, tr, l, r, h):
        #node interval [tl,tr] does not overlap with query interval [l,r]
        if r < tl or tr < l: return
        #node interval is included in the query interval
        if l <= tl and tr <= r:
            self.cnts[v] += h
        else:
            tm = (tl + tr)//2
            self.update(v*2, tl, tm, l, r, h)
            self.update(v*2+1, tm+1, tr, l, r, h)
        #node interval is included in the active interval
        if self.cnts[v] > 0:
            self.total[v] = self.xs[tr + 1] - self.xs[tl]
        else:
            self.total[v] = self.total[v*2] + self.total[v*2+1]
        return self.total[v]

class Solution:
    def rectangleArea(self, rectangles):
        #index i means the interval from xs[i] to xs[i+1]
        xs = sorted(set([x for x1, y1, x2, y2 in rectangles for x in [x1, x2]]))
        xs_i = {x:i for i, x in enumerate(xs)}
        st = SegmentTree(xs)
        L = []
        for x1, y1, x2, y2 in rectangles:
            L.append([y1, 1, x1, x2])
            L.append([y2, -1, x1, x2])
        L.sort()
        cur_y = cur_x_sum = area = 0
        for y, open_close, x1, x2 in L:
            area += (y - cur_y) * cur_x_sum
            cur_y = y
            #one index corresponds to one interval, that's why we use xs_i[x2]-1 instead of xs_i[x2]
            st.update(1, 0, len(xs) - 1, xs_i[x1], xs_i[x2]-1, open_close)
            cur_x_sum = st.total[1]

        return area % (10 ** 9 + 7)
class Solution {
      public int rectangleArea(int[][] rectangles) {
          int n = rectangles.length;
          Set<Integer> coorx = new HashSet<>();
          Set<Integer> coory = new HashSet<>();
          for (int[] rec : rectangles) {
              coorx.add(rec[0]); coorx.add(rec[2]);
              coory.add(rec[1]); coory.add(rec[3]);
          }

          Integer[] compressx = coorx.toArray(new Integer[0]);
          Arrays.sort(compressx);
          Integer[] compressy = coory.toArray(new Integer[0]);
          Arrays.sort(compressy);

          Map<Integer, Integer> mapx = new HashMap<>();
          for(int i = 0; i < compressx.length; i++) {
              mapx.put(compressx[i], i);
          }
          Map<Integer, Integer> mapy = new HashMap<>();
          for(int i = 0; i < compressy.length; i++) {
              mapy.put(compressy[i], i);
          }

          boolean[][] grid = new boolean[compressx.length][compressy.length];
          for (int[] rec: rectangles) {
              for (int x = mapx.get(rec[0]); x < mapx.get(rec[2]); x++) {
                  for (int y = mapy.get(rec[1]); y < mapy.get(rec[3]); y++) {
                      grid[x][y] = true;
                  }
              }
          }

          long res = 0L;
          for (int i = 0; i < grid.length; i++) {
              for (int j = 0; j < grid[0].length; j++) {
                  if (grid[i][j]) {
                      res += (long)(compressx[i + 1] - compressx[i]) * (compressy[j + 1] - compressy[j]);
                  }
              }
          }
          res %= 1000000007;
          return (int)res;
      }
  }
struct Point
{
    int X;
    int delta;
};

class Solution
{
public:
    int rectangleArea(vector<vector<int>>& rectangles)
    {
        map<int, vector<Point>> lines; // y -> array of Points
        for (auto&r : rectangles)
        {
            auto x1 = r[0];
            auto y1 = r[1];
            auto x2 = r[2];
            auto y2 = r[3];

            lines[y1].push_back(Point {x1, +1});
            lines[y1].push_back(Point {x2, -1});
            lines[y2].push_back(Point {x1, -1});
            lines[y2].push_back(Point {x2, +1});
        }

        long area = 0;
        int prevy = 0;
        int length = 0;

        map<int, int> scanline; // x -> delta
        for (const auto& [y, points] : lines)
        {
            area += (y - prevy) * (long)length;

            // Update scanline for new y: add new rectanhgles,
            // remove old
            for (auto point : points)
            {
                auto xdelta = scanline.find(point.X);
                if (xdelta != end(scanline))
                {
                    xdelta->second += point.delta;
                    if (xdelta->second == 0)
                        scanline.erase(xdelta);
                }
                else
                    scanline[point.X] = point.delta;
            }

            // For current y-line calc the length of
            // intersection with rectangles
            int startX = -1;
            int rectCount = 0;
            length = 0;
            for (const auto& [x, delta] : scanline)
            {
                int oldcount = rectCount;
                rectCount += delta;
                if (oldcount == 0)
                    startX = x;
                else if (rectCount == 0)
                    length += x - startX;
            }

            if (rectCount > 0)
                length += scanline.rbegin()->first - startX;

            prevy = y;
        }

        return area % (1000000007);
    }
};
var rectangleArea = function(rectangles) {
  let events = [], active = [], area = 0n;
  let mod = BigInt(1000000007);
  for (var rec of rectangles) {
    events.push([rec[1], 'open', rec[0], rec[2]]);
    events.push([rec[3], 'close', rec[0], rec[2]]);
  }  
  events = events.sort((a, b) => a[0] - b[0]);
  let y = events[0][0];
  for (var event of events) {
    let currY = event[0], type = event[1], x1 = event[2], x2 = event[3];
    let maxLength = 0, curr = -1;
    for (var ev of active) {
      curr = Math.max(curr, ev[0]);
      maxLength += Math.max(0, ev[1] - curr);
      curr = Math.max(curr, ev[1]);
    }
    area += (BigInt(maxLength) * BigInt(currY - y));
    area %= mod;
    if (type === 'open') {
      active.push([x1, x2]);
      active = active.sort((a, b) => a[0] - b[0]);
    } else {
      for (var i = 0; i < active.length; i++) {
        let e = active[i];
        if (e[0] === x1 && e[1] === x2) {
          active.splice(i, 1);
          break;
        }
      }
    }
    y = currY;
  }
  return area % mod;
};
Rectangle Area II