F - Rectangles

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1000000;

struct Event {
    int x1, x2, y, t;
    Event(int _x1, int _x2, int _y, int _t) {
        x1 = _x1, x2 = _x2, y = _y, t = _t;
    }
    Event(){}
};

int n;
int tree[MAX];
int lazy[MAX];
vector<int> values;
vector<Event> ev;

void push(int node, int start, int end) {
    tree[node] = values[end + 1] - values[start] - tree[node];
    if(start != end) {
        lazy[2 * node] ^= 1;
        lazy[2 * node + 1] ^= 1;
    }
    lazy[node] = 0;
}

void update(int node, int start, int end, int l, int r) {
    if(lazy[node]) push(node, start, end);
    if(start > r or l > end) return;
    if(l <= start and end <= r) push(node, start, end);
    else {
        int mid = (start + end) / 2;
        update(2 * node, start, mid, l, r);
        update(2 * node + 1, mid + 1, end, l, r);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

int query() {
    if(lazy[1]) push(1, 0, (int)values.size() - 1);
    return tree[1];
}

int get_pos(int x){
    return lower_bound(values.begin(), values.end(), x) - values.begin();
}

bool cmp(Event a, Event b) {
    if(a.y != b.y) return a.y < b.y;
    return a.t < b.t;
}

int32_t main() {
    scanf(" %d", &n);
    for(int i = 0; i < n; i++) {
        int x1, y1, x2, y2;
        scanf(" %d %d %d %d", &x1, &y1, &x2, &y2);
        int xmi = min(x1, x2);
        int ymi = min(y1, y2);
        int xma = max(x1, x2);
        int yma = max(y1, y2);

        ev.emplace_back(xmi, xma, ymi, -1);
        ev.emplace_back(xmi, xma, yma, 1);

        values.push_back(xmi);
        values.push_back(xma);
    }

    values.push_back(1000000007);

    sort(values.begin(), values.end());
    values.resize(unique(values.begin(), values.end()) - values.begin());

    sort(ev.begin(), ev.end(), cmp);

    long long Y = 0, ans = 0;

    for(int i = 0; i < ev.size(); i++) {
        long long s = query();
        long long aux = s * 1LL * (ev[i].y - Y);
        update(1, 0, (int)values.size() - 1, get_pos(ev[i].x1), get_pos(ev[i].x2) - 1);
        Y = ev[i].y;
        ans += aux;
    }
    cout << ans << '\n';

    return 0;
}