<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 <bits/stdc++.h>
#define x first
#define y second
using namespace std;

class Solution {
public:
    map<int, int> r;
    map<int, int> tr;
    
    struct SegmentTree {
        const pair<int, int> INF = {INT_MAX, INT_MAX};
        vector<int> a;
        vector<pair<int, int>> t;
        vector<int> push;
    
        SegmentTree(const vector<int>& data) {
            a = data;
            t.assign(4 * a.size(), {0, 0});
            push.assign(4 * a.size(), 0);
            build(0, 0, (int)a.size());
        }
    
        SegmentTree(const int size) {
            a.assign(size, 0);
            t.assign(4 * a.size(), {0, 0});
            push.assign(4 * a.size(), 0);
            build(0, 0, (int)a.size());
        }
    
        pair<int, int> f(pair<int, int> left, pair<int, int> right) {
            if (left.x == right.x) {
                return {left.x, left.y + right.y};
            }
            return min(left, right);
        }
    
        void build(int v, int l, int r) {
            if (l + 1 == r) {
                t[v].x = 0;
                t[v].y = a[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * v + 1, l, m);
            build(2 * v + 2, m, r);
            t[v] = f(t[2 * v + 1], t[2 * v + 2]);
        }
    
        void makePush(int v) {
            if (push[v] == 0) {
                return;
            }
    
            push[2 * v + 1] += push[v];
            push[2 * v + 2] += push[v];
    
            t[2 * v + 1].x += push[v];
            t[2 * v + 2].x += push[v];
    
            push[v] = 0;
        }
    
        pair<int, int> get(int v, int l, int r, int ql, int qr) {
            if (qr <= l || r <= ql) {
                return INF;
            }
    
            if (ql <= l && r <= qr) {
                return t[v];
            }
    
            makePush(v);
    
            int m = (l + r) / 2;
            return f(get(2 * v + 1, l, m, ql, qr),
                    get(2 * v + 2, m, r, ql, qr));
        }
    
        void add(int v, int l, int r, int ql, int qr, int d) {
            if (qr <= l || r <= ql) {
                return;
            }
    
            if (ql <= l && r <= qr) {
                push[v] += d;
                t[v].x += d;
                return;
            }
    
            makePush(v);
            int m = (l + r) / 2;
            add(2 * v + 1, l, m, ql, qr, d);
            add(2 * v + 2, m, r, ql, qr, d);
            t[v] = f(t[2 * v + 1], t[2 * v + 2]);
        }
    
        pair<int, int> get(int l, int r) {
            return get(0, 0, a.size(), l, r);
        }
    
        void add(int l, int r, int d) {
            add(0, 0, a.size(), l, r, d);
        }
    };
    
    struct event {
        int x, y1, y2, type;
    };

    const int MOD = 1e9 + 7;
    int rectangleArea(vector<vector<int>>& rectangles) {
        int n = rectangles.size();
        if (n == 0) {
            return 0;
        }
        vector<event> events;
        vector<int> y;
        for (int i = 0; i < n; i++) {
            int x1 = rectangles[i][0];
            int y1 = rectangles[i][1];
            int x2 = rectangles[i][2];
            int y2 = rectangles[i][3];
            y.push_back(y1);
            y.push_back(y2);
        events.push_back({min(x1, x2), min(y1, y2), max(y1, y2), 1});
        events.push_back({max(x1, x2), min(y1, y2), max(y1, y2), 2});
        }
        sort(y.begin(), y.end());
        vector<int> a(y.size());
    
        int sum = y[y.size() - 1] - y[0];
        for (int i = 0; i < y.size(); i++) {
            r[y[i]] = i;
        }
        for (int i = 0; i < (int)y.size() - 1; i++) {
            a[i] = y[i + 1] - y[i];
        }
        SegmentTree tree(a);
        sort(events.begin(), events.end(), [](const event ev1, 
        const event ev2){
            return ev1.x < ev2.x;
        });
        unsigned long long ans = 0;
        int lastx = events[0].x;
        for (int i = 0; i < events.size(); i++) {
            event ev = events[i];
            ans = (ans + (1LL * (sum - tree.get(0, y.size()).y) * 
            (ev.x - lastx) % MOD)) % MOD;
            if (ev.type == 1) {
                tree.add(r[ev.y1], r[ev.y2], 1);
            } else {
                tree.add(r[ev.y1], r[ev.y2], -1);
            }
            lastx = ev.x;
        }
        return ans;
    }
};
12400