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

typedef long long (ll);
ll mod = 1e9 + 7;

class interval {
public:
    void insert(ll a, ll b, ll &sum) {
        cout << "insert: " << a << " " << b << endl;
        cout <<endl;
        for (auto x: m)
            cout << x.first << " " << x.second[0] << " "<< x.second[1] << endl;
        cout << endl;

        auto it1 = m.lower_bound(a);
        auto it2 = m.lower_bound(b);

        if (it1!=m.begin()) {
            --it1;
            if (it1->second[0]<=a) ++it1;
        }

        if (it1==m.end() || it2==m.begin()) {
            m[a] = {b, 1};
            sum += b-a;
            return;
        }

        ll prev = -1;
        if (a<it1->first) {
            ll r = min(it1->first, b);
            m[a] = {r, 1};
            sum += r - a;
            prev = r;
        }
        while (it1!=it2) {
            ll l = it1->first;
            ll r = it1->second[0];
            ll v = it1->second[1];

            auto nxt = next(it1);
            m.erase(it1);
            sum -= r-l;
            add(l, r, v, a, b, sum);
            if (prev!=-1 && prev<l)
                add(prev, l, 0, a, b, sum);
            prev = r;
            it1 = nxt;
        }
        if (prev!=-1&&prev<b) {
            m[prev] = {b, 1};
            sum += b-prev;
        }

        cout <<endl;
        for (auto x: m)
            cout << x.first << " " << x.second[0] << " "<< x.second[1] << endl;
        cout << endl;
    }
    void add(ll l, ll r, ll v, ll a, ll b, ll &sum) {
        if (l<a && r<=b) {
            m[l] = {a, v};
            sum += a-l;
            m[a] = {r, v+1};
            sum += r-a;
        } else if (l<a && r>b) {
            m[l] = {a, v};
            sum += a-l;
            m[a] = {b, v+1};
            sum += b-a;
            m[b] = {r, v};
            sum += r-b;
        } else if (l>=a && r<=b) {
            m[l] = {r, v+1};
            sum += r-l;
        } else if (l>=a && r>b) {
            m[l] = {b, v+1};
            sum += b-l;
            m[b] = {r, v};
            sum += r-b;
        } else if (l>=b) {
            m[l] = {r, v};
            sum += r-l;
        }
    }

    void remove(ll a, ll b, ll &sum) {
        cout << "remove: " << a << " " << b << endl;
        for (auto x: m)
            cout << x.first << " " << x.second[0] << " "<< x.second[1] << endl;
        cout << endl;

        auto it1 = m.lower_bound(a);
        auto it2 = m.lower_bound(b);
        if (it1!=m.begin()) {
            --it1;
            if (it1->second[0]<=a) ++it1;
        }

        while (it1!=it2) {
            ll l = it1->first;
            ll r = it1->second[0];
            ll v = it1->second[1];

            auto nxt = next(it1);
            m.erase(it1);
            it1 = nxt;

            sum -= r-l;
            sub(l, r, v, a, b, sum);
        }
        cout <<endl;
        for (auto x: m)
            cout << x.first << " " << x.second[0] << " "<< x.second[1] << endl;
        cout << endl;
    }

    void sub(ll l, ll r, ll v, ll a, ll b, ll &sum) {
        if (l<a && r<=b) {
            m[l] = {a, v};
            sum += (a-l)*v;
            if (v>1) {
                m[a] = {r, v-1};
                sum += r-a;
            }
        } else if (l<a && r>b) {
            m[l] = {a, v};
            sum += (a-l)*v;
            if (v>1) {
                m[a] = {b, v-1};
                sum += b-a;
            }
            m[b] = {r, v};
            sum += (r-b)*v;
        } else if (l>=a && r<=b) {
            if (v>1) {
                m[l] = {r, v-1};
                sum += r-l;
            }
        } else if (l>=a && r>b) {
            if (v>1) {
                m[l] = {b, v-1};
                sum += b-l;
            }
            m[b] = {r, v};
            sum += r-b;
        }
    }

    map<ll,array<ll,2>> m;
};

class Solution {
public:
    int rectangleArea(vector<vector<int>>& A) {
        ll ans = 0;
        map<ll,vector<array<ll,3>>> m;

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

        interval inter;
        for (auto &x: A) {
            ll a = x[0], b = x[1], c = x[2], d = x[3];
            m[a].push_back({b,d,1});
            m[c].push_back({b,d,2});
        }

        ll prev = 0;
        ll sum = 0;

        for (auto [x, ys]: m) {
            ll w = x - prev;
            prev = x;
            ans += w*sum;
            ans %= mod;
            for (auto [l,h,st]: ys) {
                if (st==1) {
                    inter.insert(l,h,sum);
                } else {
                    inter.remove(l,h,sum);
                }
            }
            cout << x << " " << sum << " " << ans << endl;
        }

        return ans;
    }
};
18600