矩形面积并

题目	难度
850. 矩形面积 II	困难
3454. 分割正方形 II	困难
P5490 【模板】扫描线 & 矩形面积并

需要用到扫描线 & 特殊线段树

850. 矩形面积 II

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Solution850 {
    private static final int MOD = (int) (1e9 + 7);

    public int rectangleArea(int[][] rectangles) {
        int m = 0;
        TreeMap<Integer, Integer> mp = new TreeMap<>();
//        for (int[] sq : squares) {
//            mp.put(sq[0], 1);
//            mp.put(sq[0] + sq[2], 1);
//        }
        for (int[] re : rectangles) {
            mp.put(re[0], 1);
            mp.put(re[2], 1);
        }
        for (Map.Entry<Integer, Integer> p : mp.entrySet()) p.setValue(m++);
        int[] A = new int[m];
        for (Map.Entry<Integer, Integer> p : mp.entrySet()) A[p.getValue()] = p.getKey();
        // 离散化结束

        // 把正方形的上下边界取出来
        List<int[]> vec = new ArrayList<>();
//        for (int[] sq : squares) {
//            vec.add(new int[]{sq[1], mp.get(sq[0]) + 1, mp.get(sq[0] + sq[2]), 1});
//            vec.add(new int[]{sq[1] + sq[2], mp.get(sq[0]) + 1, mp.get(sq[0] + sq[2]), -1});
//        }
        for (int[] re : rectangles) {
            vec.add(new int[]{re[1], mp.get(re[0]) + 1, mp.get(re[2]), 1});
            vec.add(new int[]{re[3], mp.get(re[0]) + 1, mp.get(re[2]), -1});
        }
        vec.sort(Arrays::compare);

        // 求总的面积并
        long tot = 0;
        LazyInfoSegmentTree seg = new LazyInfoSegmentTree(m);
        seg.build(A, 1, 1, m - 1);
        for (int i = 0; i + 1 < vec.size(); i++) {
            // 考虑水平线 y = vec[i][0] 和 y = vec[i + 1][0] 之间的情况
            seg.modify(1, 1, m - 1, vec.get(i)[1], vec.get(i)[2], vec.get(i)[3]);
            // 求横截长度
            int len = A[m - 1] - A[0];
            // 如果最小覆盖数是 0，那么扣掉相应的长度
            if (seg.info[1].mn == 0) len -= seg.info[1].len;
            // 面积 = 横截长度 * 高度差
            tot += (long) len * (vec.get(i + 1)[0] - vec.get(i)[0]);
        }
        return (int) (tot % MOD);
    }

    // 线段树模板，只需要实现 mergeInfo 和 _do，其余都是固定的
    static class LazyInfoSegmentTree {
        static class Info {
            // mn：当前节点的最小覆盖数
            // len：满足覆盖数 = 最小覆盖数的 A[i] 之和
            // lazy：加法的懒标记
            int mn, len, lazy;

            public Info(int mn, int len, int lazy) {
                this.mn = mn;
                this.len = len;
                this.lazy = lazy;
            }
        }

        Info mergeInfo(Info a, Info b) {
            int mn = Math.min(a.mn, b.mn);
            return new Info(mn, (a.mn == mn ? a.len : 0) + (b.mn == mn ? b.len : 0), 0);
        }

        // 对节点的覆盖数整个增加 qv，只影响 mn，不影响 len
        void _do(int p, int qv) {
            info[p].mn += qv;
            info[p].lazy += qv;
        }

        int n;
        Info[] info;

        public LazyInfoSegmentTree(int n) {
            this.n = n;
            info = new Info[4 * n];
            Arrays.fill(info, new Info(0, 0, 0));
        }

        void build(int[] A, int p, int l, int r) {
            if (l == r) {
                info[p] = new Info(0, A[r] - A[r - 1], 0);
                return;
            }
            int m = (l + r) >> 1;
            build(A, p << 1, l, m);
            build(A, p << 1 | 1, m + 1, r);
            maintain(p);
        }

        void maintain(int p) {
            info[p] = mergeInfo(info[p << 1], info[p << 1 | 1]);
        }

        void spread(int p) {
            if (info[p].lazy == 0) return;
            _do(p << 1, info[p].lazy);
            _do(p << 1 | 1, info[p].lazy);
            info[p].lazy = 0;
        }

        void modify(int p, int l, int r, int ql, int qr, int qv) {
            if (ql <= l && r <= qr) {
                _do(p, qv);
                return;
            }
            spread(p);
            int m = (l + r) >> 1;
            if (ql <= m) modify(p << 1, l, m, ql, qr, qv);
            if (qr > m) modify(p << 1 | 1, m + 1, r, ql, qr, qv);
            maintain(p);
        }
    }
}

3454. 分割正方形 II

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class Solution3454 {
    // 线段树模板，只需要实现 mergeInfo 和 _do，其余都是固定的
    static class LazyInfoSegmentTree {
        static class Info {
            // mn：当前节点的最小覆盖数
            // len：满足覆盖数 = 最小覆盖数的 A[i] 之和
            // lazy：加法的懒标记
            int mn, len, lazy;

            public Info(int mn, int len, int lazy) {
                this.mn = mn;
                this.len = len;
                this.lazy = lazy;
            }
        }

        Info mergeInfo(Info a, Info b) {
            int mn = Math.min(a.mn, b.mn);
            return new Info(mn, (a.mn == mn ? a.len : 0) + (b.mn == mn ? b.len : 0), 0);
        }

        // 对节点的覆盖数整个增加 qv，只影响 mn，不影响 len
        void _do(int p, int qv) {
            info[p].mn += qv;
            info[p].lazy += qv;
        }

        int n;
        Info[] info;

        public LazyInfoSegmentTree(int n) {
            this.n = n;
            info = new Info[4 * n];
        }

        void build(int[] A, int p, int l, int r) {
            if (l == r) {
                info[p] = new Info(0, A[r] - A[r - 1], 0);
                return;
            }
            int m = (l + r) >> 1;
            build(A, p << 1, l, m);
            build(A, p << 1 | 1, m + 1, r);
            maintain(p);
        }

        void maintain(int p) {
            info[p] = mergeInfo(info[p << 1], info[p << 1 | 1]);
        }

        void spread(int p) {
            if (info[p].lazy == 0) return;
            _do(p << 1, info[p].lazy);
            _do(p << 1 | 1, info[p].lazy);
            info[p].lazy = 0;
        }

        void modify(int p, int l, int r, int ql, int qr, int qv) {
            if (ql <= l && r <= qr) {
                _do(p, qv);
                return;
            }
            spread(p);
            int m = (l + r) >> 1;
            if (ql <= m) modify(p << 1, l, m, ql, qr, qv);
            if (qr > m) modify(p << 1 | 1, m + 1, r, ql, qr, qv);
            maintain(p);
        }
    }

    public double separateSquares(int[][] squares) {
        int m = 0;
        TreeMap<Integer, Integer> mp = new TreeMap<>();
        for (int[] sq : squares) {
            mp.put(sq[0], 1);
            mp.put(sq[0] + sq[2], 1);
        }
        for (Map.Entry<Integer, Integer> p : mp.entrySet()) p.setValue(m++);
        int[] A = new int[m];
        for (Map.Entry<Integer, Integer> p : mp.entrySet()) A[p.getValue()] = p.getKey();
        // 离散化结束

        // 把正方形的上下边界取出来
        List<int[]> vec = new ArrayList<>();
        for (int[] sq : squares) {
            vec.add(new int[]{sq[1], mp.get(sq[0]) + 1, mp.get(sq[0] + sq[2]), 1});
            vec.add(new int[]{sq[1] + sq[2], mp.get(sq[0]) + 1, mp.get(sq[0] + sq[2]), -1});
        }
        vec.sort(Arrays::compare);

        // 求总的面积并
        long tot = 0;
        LazyInfoSegmentTree seg = new LazyInfoSegmentTree(m);
        seg.build(A, 1, 1, m - 1);
        for (int i = 0; i + 1 < vec.size(); i++) {
            // 考虑水平线 y = vec[i][0] 和 y = vec[i + 1][0] 之间的情况
            seg.modify(1, 1, m - 1, vec.get(i)[1], vec.get(i)[2], vec.get(i)[3]);
            // 求横截长度
            int len = A[m - 1] - A[0];
            // 如果最小覆盖数是 0，那么扣掉相应的长度
            if (seg.info[1].mn == 0) len -= seg.info[1].len;
            // 面积 = 横截长度 * 高度差
            tot += (long) len * (vec.get(i + 1)[0] - vec.get(i)[0]);
        }

        long now = 0;
        seg.build(A, 1, 1, m - 1);
        for (int i = 0; i + 1 < vec.size(); i++) {
            seg.modify(1, 1, m - 1, vec.get(i)[1], vec.get(i)[2], vec.get(i)[3]);
            int len = A[m - 1] - A[0];
            if (seg.info[1].mn == 0) len -= seg.info[1].len;
            now += (long) len * (vec.get(i + 1)[0] - vec.get(i)[0]);
            // delta 非负了，套公式
            long det = now - (tot - now);
            if (det >= 0) return vec.get(i + 1)[0] - 0.5 * det / len;
        }
        return -1;
    }
}

P5490 【模板】扫描线 & 矩形面积并

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

template<class Info, class Tag>
struct LazySegmentTree {
    const int n;
    vector<Info> info;
    vector<Tag> tag;

    LazySegmentTree(int n) : n(n), info(4 << (int) log2(n)), tag(4 << (int) log2(n)) {
    }

    LazySegmentTree(vector<Info> init) : LazySegmentTree(init.size()) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init[l - 1];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }

    void pull(int p) {
        info[p] = info[p * 2] + info[p * 2 + 1];
    }

    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }

    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }

    void rangeApply(int p, int l, int r, int ql, int qr, const Tag &v) {
        if (ql <= l && r <= qr) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (ql <= m) rangeApply(2 * p, l, m, ql, qr, v);
        if (qr > m) rangeApply(2 * p + 1, m + 1, r, ql, qr, v);
        pull(p);
    }

    void rangeApply(int l, int r, const Tag &v) {
        rangeApply(1, 1, n, l, r, v);
    }
};

struct Tag {
    ll add;

    Tag(int _rev = 0) : add{_rev} {
    }

    void apply(const Tag &t) {
        add += t.add;
    }
};

struct Info {
    int mn, len;

    Info() : mn(0), len(0) {
    }

    Info(int v, int x) : mn(v), len(x) {
    }

    void apply(const Tag &t) {
        mn += t.add;
    }
};

Info operator+(Info a, Info b) {
    Info c;
    int mn = min(a.mn, b.mn);
    c.mn = mn;
    c.len = (a.mn == mn ? a.len : 0) + (b.mn == mn ? b.len : 0);
    return c;
}

void solve() {
    int n;
    cin >> n;

    vector<array<int, 4> > rectangles(n);
    for (auto &re: rectangles) {
        cin >> re[0] >> re[1] >> re[2] >> re[3];
    }

    int m = 0;
    map<int, int> mp;
    for (const auto &re: rectangles) mp[re[0]] = mp[re[2]] = 1;
    for (auto &p: mp) p.second = m++;
    int A[m];
    for (auto &p: mp) A[p.second] = p.first;

    // 把正方形的上下边界取出来
    vector<array<int, 4> > vec;
    for (auto &re: rectangles) {
        vec.push_back({re[1], mp[re[0]] + 1, mp[re[2]], 1});
        vec.push_back({re[3], mp[re[0]] + 1, mp[re[2]], -1});
    }
    sort(vec.begin(), vec.end());

    vector<Info> init(m - 1);
    for (int i = 1; i < m; ++i) {
        init[i - 1] = Info(0, A[i] - A[i - 1]);
    }
    LazySegmentTree<Info, Tag> seg(init);

    // 求总的面积并
    ll tot = 0;
    for (int i = 0; i + 1 < vec.size(); i++) {
        // 考虑水平线 y = vec[i][0] 和 y = vec[i + 1][0] 之间的情况
        seg.rangeApply(1, 1, m - 1, vec[i][1], vec[i][2], vec[i][3]);
        // 求横截长度
        int len = A[m - 1] - A[0];
        // 如果最小覆盖数是 0，那么扣掉相应的长度
        if (seg.info[1].mn == 0) len -= seg.info[1].len;
        // 面积 = 横截长度 * 高度差
        tot += 1LL * len * (vec[i + 1][0] - vec[i][0]);
    }
    cout << tot << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    //    cin >> t;
    while (t--) solve();
    return 0;
}

（全文完）