# 850. Rectangle Area II

二维坐标系里有一些可能重叠的长方形，问它们形成的总面积。题目看着和skyline很像，重叠问题可以用排序+扫描线解。对每个x，求是第一条边的y去重后有效的长度。维持一个对所有x global的treemap让遍历到的所有y在里头排好序，长方形第一条竖边的入+1出-1; 第二条边反过来，入-1出+1，用于去除第一条边的记录, 遍历到sum > 0时记录下y和上个遍历的y差作为有效长度。比如两个有重叠的第一条边会成为\[1 1 -1 -1], 那么\[1 1], \[1-1]和\[-1-1]之间长度都会成功算入。如果当前x没有新长方形，那遍历求和会不断把所有可能的y置为0，比如例子中两个第二条边并入 \[1(-1) 1(-1) -1(1) -1(1)]。

参考自[这](https://link.zhihu.com/?target=https%3A//leetcode.com/problems/rectangle-area-ii/discuss/137941/Java-TreeMap-solution-inspired-by-Skyline-and-Meeting-Room)。

```cpp
/*
 * @lc app=leetcode id=850 lang=cpp
 *
 * [850] Rectangle Area II
 *
 * https://leetcode.com/problems/rectangle-area-ii/description/
 *
 * algorithms
 * Hard (45.33%)
 * Likes:    213
 * Dislikes: 23
 * Total Accepted:    8K
 * Total Submissions: 17.5K
 * Testcase Example:  '[[0,0,2,2],[1,0,2,3],[1,0,3,1]]'
 *
 * We are given a list of (axis-aligned) rectangles.  Each rectangle[i] = [x1,
 * y1, x2, y2] , where (x1, y1) are the coordinates of the bottom-left corner,
 * and (x2, y2) are the coordinates of the top-right corner of the ith
 * rectangle.
 * 
 * Find the total area covered by all rectangles in the plane.  Since the
 * answer may be too large, return it modulo 10^9 + 7.
 * 
 * 
 * 
 * Example 1:
 * 
 * 
 * Input: [[0,0,2,2],[1,0,2,3],[1,0,3,1]]
 * Output: 6
 * Explanation: As illustrated in the picture.
 * 
 * 
 * Example 2:
 * 
 * 
 * Input: [[0,0,1000000000,1000000000]]
 * Output: 49
 * Explanation: The answer is 10^18 modulo (10^9 + 7), which is (10^9)^2 =
 * (-7)^2 = 49.
 * 
 * 
 * Note:
 * 
 * 
 * 1 <= rectangles.length <= 200
 * rectanges[i].length = 4
 * 0 <= rectangles[i][j] <= 10^9
 * The total area covered by all rectangles will never exceed 2^63 - 1 and thus
 * will fit in a 64-bit signed integer.
 * 
 */
class Solution {
public:
    class Point {
    public:
        int x, y, val;
        Point(int x, int y, int val): x(x), y(y), val(val) {}
    };
    int rectangleArea(vector<vector<int>>& rectangles) {
        const int M = 1000000007;
        vector<Point> points;
        for (const auto &r : rectangles) {
            points.push_back(Point(r[0], r[1], 1));
            points.push_back(Point(r[0], r[3], -1));
            points.push_back(Point(r[2], r[1], -1));
            points.push_back(Point(r[2], r[3], 1));
        }
        sort(points.begin(), points.end(), [](Point &a, Point &b) {
            return a.x < b.x;
        });
        const auto cal_y = [](map<int, int> &m) {
            int res = 0, pre = -1, sum = 0;
            for (const auto &p : m) {
                if (sum > 0) res += p.first - pre;
                sum += p.second;
                pre = p.first;
            }
            return res;
        };
        map<int, int> m;
        const int N = points.size();
        int pre_x = -1, pre_y = -1, res = 0;
        for (int i = 0; i < N; ++i) {
            Point &p = points[i];
            if (!m.count(p.y)) m[p.y] = 0;
            m[p.y] += p.val;
            if (i == N - 1 || points[i + 1].x > p.x) {
                if (pre_x > -1) {
                    res += ((long)pre_y * (p.x - pre_x)) % M;
                    res %= M;
                }
                pre_y = cal_y(m);
                pre_x = p.x;
            }

        }
        return res;
    }
};


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/array_and_numbers/sao-miao-xian/meeting-rooms-ii/850.-rectangle-area-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.