CF gym101982F: Rectangles

#include"./template/headers.hpp"

//#define MULTI_TASKCASE
using namespace abb;
using namespace output;
using namespace rit;
using namespace wit;

inline void init() {

}

struct node {
    int v, d;
    node *l, *r;
    void pull() {
        v = (l ? l->v : 0) + (r ? r->v : 0);
    }
    void push(int L, int R) {
        if (!d) return;
        d = 0, v = (R - L) - v;
        if (R - L == 1) return;
        if (!l) l = new node;
        if (!r) r = new node;
        l->d = true, r->d = true;
    }
    node(): v(0), d(0) {
        l = r = nullptr;
    }
}*root = nullptr;

#define m ((l + r) >> 1)
constexpr int L = 0, R = 1e9 + 5;

void reverse(int ql, int qr, node*& cur = root, int l = L, int r = R) {
    if (!cur) cur = new node;
    else cur->push(l, r);
    if (qr <= l || r <= ql) return;
    if (ql <= l && r <= qr) {
        cur->d = true, cur->push(l, r);
//      debug(l, r, cur->v);
        return;
    }
    reverse(ql, qr, cur->l, l, m);
    reverse(ql, qr, cur->r, m, r);
    cur->pull();
}
inline int query() {return root ? (root->push(L, R), root->v) : 0;}
#undef m

inline void solve() {
    int n; cin >> n;
    using line = tuple<int, int, int>;
    V<line> v(n << 1);
    for (int i = 0; i != n; i++) {
        static int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (y1 > y2) swap(y1, y2);
        v[i << 1    ] = {x1, y1, y2};
        v[i << 1 | 1] = {x2, y1, y2};
    }
    sort(v.begin(), v.end());
    ll sum = 0, cur = 0;
    for (const auto& i : v) {
        static int x, l, r;
        tie(x, l, r) = i;
        sum += 1LL * (x - cur) * query();
        reverse(l, r), cur = x;
//      debug(x, l, r, query());
    }
    cout << sum << endl;
}

main() {
    ios::sync_with_stdio(false);
    init();
    int t = 1;
#ifdef MULTI_TASKCASE
    cin >> t; cin.ignore();
#endif
    while (t--) solve();
    return 0;
}