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

class Solution {
private:
    struct Rect {
        const int x1, y1;
        const int x2, y2;

        Rect(const std::vector<int>& coord) :
            x1(coord[0]),
            y1(coord[1]),
            x2(coord[2]),
            y2(coord[3]) {
            
        }
    };

    class XYMap {
        typedef std::map<int, int> YMap;
        typedef std::map<int, YMap> XMap;
        XMap _xmap;

        void splitX(int x) {
            XMap::iterator it = _xmap.lower_bound(x);
            if (it != _xmap.end() && it->first == x)
                return;
            it--;
            _xmap.emplace(x, it->second);
        }

        static void splitY(int y, YMap& ymap) {
            YMap::iterator it = ymap.lower_bound(y);
            if (it != ymap.end() && it->first == y)
                return;
            it--;
            ymap.emplace(y, it->second);
        }

        static int sumYRanges(const YMap& ymap) {
            if (ymap.size() < 2) {
                return 0;
            }
            auto it1 = ymap.begin();
            it1++;
            auto it2 = it1;
            it2++;
            auto end = ymap.end();
            int sum = 0;
            for (; it1 != end && it2 != end; it1++, it2++) {
                auto rects = it1->second;
                int len = rects > 0 ? it2->first - it1->first : 0;
                //printf("Y[%d, %d] len %d", it1->first, it2->first, len);
                sum += len;
            }
            return sum;
        }

    public:
        XYMap() {
            YMap ymap;
            ymap.emplace(INT_MIN, 0);
            _xmap.emplace(INT_MIN, ymap);
        }

         void add(const Rect& rect) {
            splitX(rect.x1);
            splitX(rect.x2);
            for (XMap::iterator itX = _xmap.lower_bound(rect.x1); itX != _xmap.lower_bound(rect.x2); itX++) {
                YMap& ymap = itX->second;
                splitY(rect.y1, ymap);
                splitY(rect.y2, ymap);
                for (YMap::iterator itY = ymap.lower_bound(rect.y1); itY != ymap.lower_bound(rect.y2); itY++) {
                    itY->second++;
                }
            }
        }

        int area() const {
            if (_xmap.size() < 2) {
                return 0;
            }

            std::uint64_t sum = 0;
            auto it1 = _xmap.begin();
            it1++;
            auto it2 = it1;
            it2++;
            auto end = _xmap.end();
            for (; it1 != end && it2 != end; it1++, it2++) {
                int xlen = it2->first - it1->first;
                int ylen = sumYRanges(it1->second);
                sum += (std::uint64_t)xlen * ylen;
                sum = sum % 1000000007;
            }
            return (int) sum;
        }
    };

public:
    int rectangleArea(std::vector<std::vector<int>>& rectangles) {
        XYMap xymap;
        for (auto it=rectangles.begin(); it!=rectangles.end(); it++) {
            auto& coord = *it;
            Rect rect(coord);
            xymap.add(rect);
        }
        //printf("XYMap: %s", xymap.toString().c_str());
        return xymap.area();
    }
};


19200