850. Rectangle Area II

You are given a 2D array of axis-aligned rectangles. Each rectangle[i] = [xi1, yi1, xi2, yi2] denotes the ith rectangle where (xi1, yi1) are the coordinates of the bottom-left corner, and (xi2, yi2) are the coordinates of the top-right corner.

Calculate the total area covered by all rectangles in the plane. Any area covered by two or more rectangles should only be counted once.

Return the total area. Since the answer may be too large, return it modulo 109 + 7.

#define MAX_N 505
#define INF 987654321
#define ll long long
#define pll pair<ll, ll>
#define vpll vector<pll>
#define vall3 vector<array<ll,3>>
#define all5 array<ll,5>
#define vall5 vector<all5>
#define vll vector<ll>
#define vs vector<string>
#define usll unordered_set<ll>
#define vvs vector<vs>
#define vvll vector<vll>
#define all(a) begin(a), end(a)

using namespace std;
struct Seg {
    ll mi, ma, count;
    Seg *l, *r;
    Seg(vector<ll> A, int left, int right): count(0), l(nullptr), r(nullptr) {
        mi = A[left], ma = A[right];
        if(left == right) return ;
        int m = (left + right) / 2;
        if(left + 1 == right) {
            l = new Seg(A, left, m);
            r = new Seg(A, m + 1, right);
        } else {
            l = new Seg(A, left, m);
            r = new Seg(A, m, right);
        }
    }
    ll query(int from, int to) {
        if(mi > to or ma < from) return 0;
        if(count) return ma - mi;
        return (l ? l->query(from, to) : 0) + (r ? r->query(from, to) : 0);
    }

    void update(int from, int to, int val) {
        if(mi > to or ma < from) return ;
        if(from <= mi and ma <= to) {
            count += val;
        }
        if(l) l->update(from, to, val);
        if(r) r->update(from, to, val);
    }
};

struct Line {
    ll x, y1, y2;
    bool eof;

    bool operator < (const Line& other) {
        return x < other.x;
    }
};

class Solution {
public:
    int rectangleArea(vector<vector<int>>& R) {
        vector<Line> l;
        unordered_set<ll> yus;
        for(auto& r : R) {
            int x1 = r[0], y1 = r[1], x2 = r[2], y2 = r[3];
            l.push_back({x1, y1, y2, false});
            l.push_back({x2, y1, y2, true});

            yus.insert(y1);
            yus.insert(y2);
        }

        vll y(all(yus));
        sort(all(y));
        sort(all(l));

        Seg* seg = new Seg(y, 0, y.size() - 1);
        ll res = 0, x = l[0].x, mod = 1e9 + 7;
        seg->update(l[0].y1, l[0].y2, 1);

        for(int i = 1; i < l.size(); i++) {
            res = (res + (l[i].x - x) * seg->query(y[0], y.back())) % mod;
            seg->update(l[i].y1, l[i].y2, l[i].eof ? -1 : 1);
            x = l[i].x;
        }

        return res;
    }
};