<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>

#include <iostream>
#include <random>
#include <array>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <bitset>

#include <math.h>

using namespace std;

int const mod = 1e9 + 7;

class SegmentTree {
  public:
    SegmentTree(vector<int>& sortedYs) : sortedYs_(sortedYs), freq_(sortedYs.size() * 4), len_(sortedYs.size() * 4) {}

    int Query() const {
      return len_[1];
    }

    void Update(int l, int r, int delta) {
      Update(1, 0, static_cast<int>(sortedYs_.size()) - 2, l, r, delta);
    }

  private:
    void Update(int node, int tl, int tr, int l, int r, int delta) {
      if (l > r) return;

      if (tl == l && r == tr) {
        freq_[node] += delta;
      } else {
        int tm = tl + (tr - tl) / 2;

        Update(node * 2, tl, tm, l, min(r, tm), delta);
        Update(node * 2 + 1, tm + 1, tr, max(l, tm + 1), r, delta);
      }

      if (freq_[node] > 0) {
        len_[node] = sortedYs_[tr + 1] - sortedYs_[tl];
      } else {
        if (tl == tr) {
          len_[node] = 0;
        } else {
          len_[node] = len_[node * 2] + len_[node * 2 + 1];
        }
      }
    }

    vector<int>& sortedYs_;
    vector<int> freq_;
    vector<int> len_;
};

class Solution {
  public:
    struct Event {
      int type;
      int x;
      int y1;
      int y2;

      bool operator<(Event const& other) const {
        return x < other.x;
      }
    };

    int rectangleArea(vector<vector<int>>& rectangles) {
      vector<Event> events;
      set<int> ys;

      for (auto& rect: rectangles) {
        int x1 = rect[0];
        int y1 = rect[1];
        int x2 = rect[2];
        int y2 = rect[3];

        events.emplace_back(+1, x1, y1, y2);
        events.emplace_back(-1, x2, y1, y2);

        ys.insert(y1);
        ys.insert(y2);
      }

      sort(events.begin(), events.end());

      vector<int> sortedYs(ys.begin(), ys.end());
      sortedYs.push_back(sortedYs.back() + 1);

      unordered_map<int, int> yToIdx;
      for (int i = 0; i < sortedYs.size(); ++i) yToIdx[sortedYs[i]] = i;

      SegmentTree st(sortedYs);

      int prevX = events[0].x - 1;
      int area = 0;

      for (auto& event: events) {
        area = (area + 1LL * (event.x - prevX) * st.Query()) % mod;

        st.Update(yToIdx[event.y1], yToIdx[event.y2] - 1, event.type); 

        prevX = event.x;
      }

      return area;
    }
};

12600