850. 矩形面积 II：扫描线+离散化+线段树

Difficulty: hard
标签: 扫描线, 离散化, 线段树

题目链接

力扣

题目解析

面试代码

/*
 * x轴方向使用扫描线，y轴方向使用线段树维护扫描线的长度和每个区间覆盖的次数。由于y轴方向很大，所以需要对区间进行离散化（让一个区间表示更长的长度）
 * y轴有2n-1个区间，x轴保存的是区间的起始坐标，如何快速知道x轴上的起始坐标是离散后的起始区间是一个难点。
 * 我想到的方法是去保存每个坐标是哪个区间的开始，哪个区间的结束。
 * 线段树节点维护区间的访问次数和长度，如果访问次数等于0，长度就是其左右节点的长度和，否则就是自己维护的区间的大小，每个节点的访问次数是大于等于0的
 */
class Solution {
    using ll = long long;
    static constexpr ll MOD = 1e9 + 7;
    vector<int> len;    //长度
    enum FLAG {
        IN = 1, OUT = -1
    };
    map<int, vector<tuple<int, int, int>>> x;
    void init(vector<vector<int>> &rectangles) {
        //1.1.对y轴区间进行离散化，并记录每个区间的长度，以及边界到对应区间的映射
        set<int> y;
        unordered_map<int, int> y2idx;   //映射
        for (auto &rect : rectangles) {
            y.insert(rect[1]);
            y.insert(rect[3]);
        }
        len.resize(y.size());
        auto iterY = y.begin();
        int last = *iterY++;
        int idx = 0;
        for (; iterY != y.end(); ++iterY) {
            y2idx[last] = ++idx;
            len[idx] = *iterY - last;
            last = *iterY;
        }
        y2idx[last] = ++idx;

        //1.2 对x轴进行排序，记录修改的区间，和进出标志
        for (auto &rect : rectangles) {
            x[rect[0]].emplace_back(y2idx[rect[1]], y2idx[rect[3]] - 1, IN);
            x[rect[2]].emplace_back(y2idx[rect[1]], y2idx[rect[3]] - 1, OUT);
        }
    }
    class SegmentTree {
        class Node {
        public:
            int cnt = 0, sum = 0, l, r, len, mid;
        };
        int n_;
        vector<int> const &len_;
        vector<Node> nodes_;
        int build(int idx, int l, int r) {
            auto &node = nodes_[idx];
            node.l = l; node.r = r;
            int mid = (l + r) >> 1;
            node.mid = mid;
            if (l == r) {
                return node.len = len_[l];
            }
            return node.len = build(idx << 1, l, mid) + build((idx << 1) + 1, mid + 1, r);
        }

        int s_, e_, flag_;
        void pushUp(int idx, Node &node) {
            if (node.cnt > 0) {
                node.sum = node.len;
            } else if (node.l != node.r) {
                node.sum = nodes_[idx << 1].sum + nodes_[(idx << 1) + 1].sum;
            } else {
                node.sum = 0;
            }
        }
        void modify(int idx) {
            auto &node = nodes_[idx];
            if (node.l >= s_ && node.r <= e_) {
                node.cnt += flag_;
                pushUp(idx, node);
                return;
            }
            if (node.mid >= s_) modify(idx << 1);
            if (node.mid < e_) modify((idx << 1) + 1);
            pushUp(idx, node);
        }
    public:
        SegmentTree(int n, vector<int> len): nodes_(n << 2), n_(n), len_(len) {
            build(1, 1, n);
        }
        void modify(int s, int e, int flag) {
            s_ = s; e_ = e; flag_ = flag;
            modify(1);
        }
        int query() {
            return nodes_[1].sum;
        }
    };
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        int n = rectangles.size();
        //1.初始化
        init(rectangles);

        SegmentTree segmentTree(len.size() - 1, len);
        int last = x.begin()->first;
        ll ans = 0;
        //2.扫描树扫描
        for (auto &&[now, tps] : x) {
            ans += static_cast<ll>(now - last) * segmentTree.query() % MOD;
            ans %= MOD;
            for (auto &&[l, r, flag] : tps) segmentTree.modify(l, r, flag);
            last = now;
        }

        //3.返回结果
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

思路描述

这个题目一看就有很浓厚的计算几何的气息，我没有什么思路，直接去看了题解，看了以后不禁感叹思路的灵活。主体的算法使用的是扫描线，之前没有接触过这种思路，但是了解了以后又觉得很符合直觉，将二维的问题转化为一维的问题，由线到面，将多个矩形的面积求解转换为所有矩形的某个方向的边移动的范围。主要的诀窍就在于对于这个线的长度的维护。

如果坐标的范围较小的时候，直接用一个线段树进行维护就可以。但是现在区间的范围很大，如何对其进行处理就很有技巧。一般对于这种数据范围很大但是我们又不得不处理的情况，我们会考虑离散化：一般的思路一个小节点维护的区间长度是1（原子区间），但是实际上矩形的个数远小于坐标的范围，如果将每个矩阵的（y1,y2）放到一起，最多有2n个修改的点，这2n个点最多组成2n-1个区间，而对2n-1个区间进行维护我们是可以接受的。这个过程就是离散化，通过实际数据划分更大的原子区间。

在确定离散化后我们就要考虑如何进行维护，如果笨一些就直接用一个数组进行维护，每次修改区间就先二分找到影响的区间范围（或者哈希记录一下），然后O(n)修改。但是如果n比较大（大于1e4），那么O(n^2)的复杂度就有可能超时。更优秀的做法是用线段树进行维护，复杂度是O(nlogn)。

如果确定使用线段树，那么在离散化的时候就必须注意到线段树的节点编号是从1开始的。

对于线段树的实现：

• 在OI wiki上介绍了为什么线段树的空间复杂度是O(4n)
• 权衡了许久是否需要记录每个节点的覆盖的范围和左右孩子的边界，最终还是决定进行记录，因为不记录的话每次操作都需要进行计算，我觉得难以忍受，而且还需要不断进行传参，其实时空复杂度都不会优化
• 以前也见过线段树用来处理区间查询、区间修改的题目，但是这些题目修改和查询的往往是相同的值，在这个题目中其实是不同的值，不过是修改的值对查询的值有影响，因此很重要的就是每个节点保存需要查询的值和修改的值，然后在每次修改的时候自底向上（pushUP）的动态维护需要查询的值。

仔细看了一下题解，他的离散化比我这边简洁许多，我用了unordered_map和set帮助处理，但是好像常数有些大。

代码优化

struct Segtree {
    int cover;
    int length;
    int max_length;
    int l, r, mid;
};

class Solution {
public:
    int rectangleArea(vector<vector<int>>& rectangles) {
        int n = rectangles.size();
        for (const auto& rect: rectangles) {
            // 下边界
            hbound.push_back(rect[1]);
            // 上边界
            hbound.push_back(rect[3]);
        }
        sort(hbound.begin(), hbound.end());
        hbound.erase(unique(hbound.begin(), hbound.end()), hbound.end());
        int m = hbound.size();
        // 线段树有 m-1 个叶子节点，对应着 m-1 个会被完整覆盖的线段，需要开辟 ~4m 大小的空间
        tree.resize(m * 4 + 1);
        init(1, 1, m - 1);

        vector<tuple<int, int, int>> sweep;
        for (int i = 0; i < n; ++i) {
            // 左边界
            sweep.emplace_back(rectangles[i][0], i, 1);
            // 右边界
            sweep.emplace_back(rectangles[i][2], i, -1);
        }
        sort(sweep.begin(), sweep.end());

        long long ans = 0;
        for (int i = 0; i < sweep.size(); ++i) {
            int j = i;
            while (j + 1 < sweep.size() && get<0>(sweep[i]) == get<0>(sweep[j + 1])) {
                ++j;
            }
            if (j + 1 == sweep.size()) {
                break;
            }
            // 一次性地处理掉一批横坐标相同的左右边界
            for (int k = i; k <= j; ++k) {
                auto&& [_, idx, diff] = sweep[k];
                // 使用二分查找得到完整覆盖的线段的编号范围
                int left = lower_bound(hbound.begin(), hbound.end(), rectangles[idx][1]) - hbound.begin() + 1;
                int right = lower_bound(hbound.begin(), hbound.end(), rectangles[idx][3]) - hbound.begin();
                update(1, left, right, diff);
            }
            ans += static_cast<long long>(tree[1].length) * (get<0>(sweep[j + 1]) - get<0>(sweep[j]));
            i = j;
        }
        return ans % static_cast<int>(1e9 + 7);
    }

    void init(int idx, int l, int r) {
        tree[idx].cover = tree[idx].length = 0;
        tree[idx].l = l; tree[idx].r = r;
        int mid = (l + r) / 2;
        tree[idx].mid = mid;
        if (l == r) {
            tree[idx].max_length = hbound[l] - hbound[l - 1];
            return;
        }
        
        init(idx * 2, l, mid);
        init(idx * 2 + 1, mid + 1, r);
        tree[idx].max_length = tree[idx * 2].max_length + tree[idx * 2 + 1].max_length;
    }

    void update(int idx, int ul, int ur, int diff) {
        auto &node = tree[idx];
        if (node.l > ur || node.r < ul) {
            return;
        }
        if (ul <= node.l && node.r <= ur) {
            node.cover += diff;
            pushup(idx);
            return;
        }
        update(idx * 2, ul, ur, diff);
        update(idx * 2 + 1, ul, ur, diff);
        pushup(idx);
    }

    void pushup(int idx) {
        auto &node = tree[idx];
        if (node.cover > 0) {
            node.length = node.max_length;
        }
        else if (node.l == node.r) {
            node.length = 0;
        }
        else {
            node.length = tree[idx * 2].length + tree[idx * 2 + 1].length;
        }
    }

private:
    vector<Segtree> tree;
    vector<int> hbound;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

题解的离散化就是sort+unique+erase一套组合拳，后面的x轴也直接是vector+二分。的确是比我的这个快一些。

我尝试了一下我记录左右边界和中间的边界会不会提速，好像是会提速一些，但是Leetcode的时间并不准， 不过我觉得还是会优化一点点的。

面试总结

优点

• 在理解思路以后能够自己实现

缺点

• 对于线段树不熟悉，没有想到扫描线的思路（其实还是很自然的，不过是起了个好听的名字）

改进方案

多熟悉熟悉这类数据结构，对于代码能力是很好的提升。有时间证明一下时空复杂度。