tioj 1224 矩形覆蓋問題AC

using namespace std;
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <utility>
#include <bitset>
#include <memory.h>
#include <set>

#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define LL long long

/*
8e7 so dian
FHVirus so dian
youou so dian
KYW so dian
hubert so dian
jass so dian
tingyu so dian
*/

//IO
#define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
#define endl '\n'

//workspace
#define mid (LB+RB)/2

struct BOUND{
    int l,r;
    int b;
    int val;
}boundary[200200];

pii seg[4000400];
int lazy[4000400];
void constructTree(int cur,int LB,int RB){
    seg[cur].S = RB - LB + 1;

    if (LB == RB)
        return;

    constructTree(cur*2,LB,mid);
    constructTree(cur*2+1,mid+1,RB);
}

void push(int cur,int LB,int RB){
    if (lazy[cur]){
        if (LB != RB){
            lazy[cur*2] += lazy[cur];
            lazy[cur*2+1] += lazy[cur];
        }
        seg[cur].F += lazy[cur];
        lazy[cur] = 0;
    }
}

void modify(int l,int r,int val,int cur,int LB,int RB){
    push(cur,LB,RB);
    //cout << l << ' ' << r << ' ' << LB << ' ' << RB << ' ' << seg[cur].F << '\n';

    if (l == LB && r == RB){
        if (LB != RB){
            lazy[cur*2] += val;
            lazy[cur*2+1] += val;
        }
        seg[cur].F += val;

        //cout << LB << ' ' << RB << ' ' << seg[cur].F << ' ' << seg[cur].S << '\n';

        return;
    }

    if (r <= mid){
        modify (l,r,val,cur*2,LB,mid);
    }
    else if (l > mid){
        modify (l,r,val,cur*2+1,mid+1,RB);
    }
    else{
        modify (l,mid,val,cur*2,LB,mid);
        modify (mid+1,r,val,cur*2+1,mid+1,RB);
    }

    push(cur*2,LB,mid);
    push(cur*2+1,mid+1,RB);
    if (seg[cur*2].F == seg[cur*2+1].F)
        seg[cur] = {seg[cur*2].F,seg[cur*2].S+seg[cur*2+1].S};
    else
        seg[cur] = seg[cur*2].F < seg[cur*2+1].F ? seg[cur*2] : seg[cur*2+1];

    //cout << LB << ' ' << RB << ' ' << seg[cur].F << ' ' << seg[cur].S << '\n';
}

int main(){
    //theyRSOOOOOOOOODIAN
    int n;

    cin >> n;
    constructTree(1,1,1e6);

    for (int i=0;i<n*2;i += 2){
        int l,r,d,u;

        cin >> l >> r >> d >> u;
        boundary[i] = {l+1,r,d,1};
        boundary[i+1] = {l+1,r,u,-1};
    }
    sort (boundary,boundary+2*n,[](BOUND A,BOUND B){return A.b < B.b;});

    LL area = 0;

    for (int i=0,ind=0;i<1000000;++i){
        while (boundary[ind].b == i && ind < n*2){
            modify (boundary[ind].l,boundary[ind].r,boundary[ind].val,1,1,1000000);
            ++ind;
        }

        area += (int)(1e6) - (seg[1].F ? 0 : seg[1].S);
    }

    cout << area;

    return 0;
}