<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 <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

class Node {
public:
    int start, end, count;
    long total;
    vector<int> X;
    Node* left;
    Node* right;

    Node(int start, int end, const vector<int>& X) : start(start), end(end), X(X), count(0), total(0), left(nullptr), right(nullptr) {}

    int getRangeMid() {
        return start + (end - start) / 2;
    }

    Node* getLeft() {
        if (!left) left = new Node(start, getRangeMid(), X);
        return left;
    }

    Node* getRight() {
        if (!right) right = new Node(getRangeMid(), end, X);
        return right;
    }

    long update(int i, int j, int val) {
        if (i >= j) return 0;
        if (start == i && end == j) {
            count += val;
        } else {
            getLeft()->update(i, min(getRangeMid(), j), val);
            getRight()->update(max(getRangeMid(), i), j, val);
        }

        if (count > 0) {
            total = X[end] - X[start];
        } else {
            total = getLeft()->total + getRight()->total;
        }

        return total;
    }
};

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        int OPEN = 1, CLOSE = -1;
        vector<vector<int>> events;
        set<int> Xvals;

        for (const auto& rec : rectangles) {
            if (rec[0] < rec[2] && rec[1] < rec[3]) {
                events.push_back({rec[1], OPEN, rec[0], rec[2]});
                events.push_back({rec[3], CLOSE, rec[0], rec[2]});
                Xvals.insert(rec[0]);
                Xvals.insert(rec[2]);
            }
        }

        sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

        vector<int> X(Xvals.begin(), Xvals.end());
        map<int, int> Xi;
        for (int i = 0; i < X.size(); ++i) {
            Xi[X[i]] = i;
        }

        Node* active = new Node(0, X.size() - 1, X);
        long ans = 0;
        long cur_x_sum = 0;
        int cur_y = events[0][0];

        for (const auto& event : events) {
            int y = event[0], typ = event[1], x1 = event[2], x2 = event[3];
            ans += cur_x_sum * (y - cur_y);
            cur_x_sum = active->update(Xi[x1], Xi[x2], typ);
            cur_y = y;
        }

        ans %= 1'000'000'007;
        return static_cast<int>(ans);
    }
};

20400