Pasted

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define SZ(x) (int)(x.size())
 
struct seg{
    int x, y1, y2;
    int del;//1 -> add, -1 -> minus
}arr[200005];
bool cmp(seg a, seg b){
    return a.x < b.x;
}
 
struct node{
    node *lch, *rch;
    int l, r, mid, tag, minval, cnt;//we have cnt minval
    node(int L, int R){
        l = L; r = R;
        mid = (l+r) / 2;
        tag = minval = 0;
        cnt = r-l+1;
        if(l != r)lch = new node(l, mid);
        else lch = nullptr;
        if(l != r)rch = new node(mid+1, r);
        else rch = nullptr;
    }
    void pushtag(){
        lch->tag += tag;
        rch->tag += tag;
        lch->minval += tag;
        rch->minval += tag;
        tag = 0;
    }
    void add(int L, int R, int V){
        //cout << l << ' ' << L << ' ' << r << ' ' << R << '\n';
        if(L == l && R == r){
            minval += V;
            tag += V;
            return;
        }
        if(lch == nullptr || rch == nullptr)return;// test
        pushtag();
        if(L <= mid)lch->add(L, min(R, mid), V);
        if(R > mid)rch->add(max(L, mid+1), R, V);
        minval = min(lch->minval, rch->minval);
        if(lch->minval == rch->minval)cnt = lch->cnt + rch->cnt;
        else if(minval == lch->minval)cnt = lch->cnt;
        else if(minval == rch->minval)cnt = rch->cnt;
        //cout << l << ' ' << r << ' ' << cnt << ' ' << minval << endl;;
    }
};
 
node *root;
 
int32_t main(){
    int n;
    cin >> n;
    root = new node(1, 1000000);
    for(int i = 0; i < n; ++i){
        int l,r,d,u;
        cin >> l >> r >> d >> u;
        arr[i<<1] = {.x = l, .y1 = d, .y2 = u, .del = 1};
        arr[i<<1|1] = {.x = r, .y1 = d, .y2 = u, .del = -1};
    }
    n *= 2;
    sort(arr, arr+n, cmp);
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(i != 0){
            if(root->minval != 0)ans += (arr[i].x-arr[i-1].x) * (root->r-root->l+1);
            else ans += (arr[i].x-arr[i-1].x) * (root->r-root->l+1 - root->cnt);
            //cout << arr[i].x-arr[i-1].x << ' ' << root->r-root->l+1 - root->cnt << ' ' << ans << '\n';
        }
        root->add(arr[i].y1+1, arr[i].y2, arr[i].del);
        //cout << arr[i].x << ' ' << arr[i].y1 << ' ' << arr[i].y2 << ' ' << arr[i].del << '\n';;
    }
    cout << ans << '\n';
    return 0;
}