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

class Solution {
    public:
    typedef long long ll;

    class event {
        public: 
            int val, type, id;
            event(int _v, int _t, int _id)
            : val(_v), type(_t), id(_id) {}
    };

    class SegmentTree {
        public: 
            vector<ll> data, cnt;
            int rangesize;
            long long mod = 1000000007;
            unordered_map<int, ll> yval, yvalr;

            SegmentTree (
                int n,
                unordered_map<int, ll>& _yval,
                unordered_map<int, ll>& _yvalr
            ) {
                yval = _yval; yvalr = _yvalr;
                rangesize = pow(2, (int)log2(n) + 1);
                int treesize = (2 * rangesize)  - 1;
                data.resize(treesize, 0); 
                cnt.resize(treesize, 0);
            }

            void update_internal (int id, int rstart, int rend, int start, int end, int val) {
                if (rend <= start  || end <= rstart) return;
                else if (start <= rstart && rend <= end) {
                    cnt[id] += val; 
                    if (cnt[id]>0) data[id] = yvalr[rend] - yvalr[rstart];
                    else {
                        if ((rend-rstart) == 1) data[id] = 0;
                        else data[id] = (data[2*id + 1] + data[2*id + 2]) % mod;
                    }
                }
                else {
                    int mid = rstart + (rend - rstart) / 2;
                    update_internal (2 * id + 1, rstart, mid, start, end, val);
                    update_internal( 2 * id + 2, mid, rend, start, end, val);
                    if (cnt[id] == 0) data[id] = (data[2*id + 1] + data[2*id + 2]) % mod;
                }
            }
            
            void update(int start, int end, int val) {
                update_internal(0, 0, rangesize, start, end, val);
        }

            ll fetch() {return data[0];}
    };

    ll solve (vector<vector<int>>& rectangles) {
        long long mod = 1000000007;

        vector<event> events; set<ll> yc;
        for (int i = 0; i < rectangles.size(); i++) {
            auto curr = rectangles[i];
            events.push_back(event(curr[0], +1, i));
            events.push_back(event(curr[2], -1, i));
            yc.insert(curr[1]); yc.insert(curr[3]);
        }

        auto comp = [&](auto& e1, auto& e2){
            if (e1.val != e2.val) return e1.val < e2.val;
            else if (e1.type != e1.type) return e1.type > e2.type;
            else return e1.id < e2.id; 
        };

        sort(events.begin(), events.end(), comp);
        unordered_map<int, ll> yval, yvalr;
        int id = 0; 
        for (int y: yc) {
            yval[y] = id; yvalr[id] = y; id++;
        }

        SegmentTree segtree(id - 1, yval, yvalr);

        long long ans = 0;
        long long cx = -1;
        for (auto evnt : events) {
            auto& rec = rectangles[evnt.id];
            ll ylen = segtree.fetch();
            ans  = (ans + ylen * (evnt.val - cx)) % mod;
            cout << ylen << endl;
            if (evnt.type == 1) {
                segtree.update(yval[rec[1]], yval[rec[3]], 1);
            } else {
                segtree.update(yval[rec[1]], yval[rec[3]], -1);
            }

            cx = evnt.val;
        }
        
        return ans;
    }

    int rectangleArea(vector<vector<int>>& rectangles) {
        return solve(rectangles);
    }
};
13900