玄关求调

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int n,lx,ly;
long long x1[100005],x2[100005],y1_[100005],y2_[100005];
long long tx[200005],ty[200005],ans;
vector<int>up[200005],dn[200005];
struct Tree{
    int l,r,mn,lz;
};
struct Seg{
    Tree t[800005];
    void push_up(int x){
        t[x].mn=min(t[x*2].mn,t[x*2+1].mn);
        return;
    }
    void push_down(int x){
        if(t[x].lz){
            t[x*2].mn+=t[x].lz;
            t[x*2+1].mn+=t[x].lz;
            t[x*2].lz+=t[x].lz;
            t[x*2+1].lz+=t[x].lz;
            t[x].lz=0;
        }
        return;
    }
    void build(int x,int l,int r){
        t[x].l=l,t[x].r=r;
        if(l==r)return;
        build(x*2,l,(l+r)/2),build(x*2+1,(l+r)/2+1,r);
        push_up(x);
        return;
    }
    void update(int x,int l,int r,int k){
        if(t[x].r<l || r<t[x].l)return;
        if(l<=t[x].l && t[x].r<=r){
            t[x].mn+=k;
            t[x].lz+=k;
            return;
        }
        push_down(x);
        update(x*2,l,r,k),update(x*2+1,l,r,k);
        push_up(x);
        return;
    }
    long long query(int x,int l,int r){
        if(t[x].r<l || r<t[x].l)return 0;
        if(l<=t[x].l && t[x].r<=r && t[x].mn>0)return tx[t[x].r]-tx[t[x].l-1];
        push_down(x);
        return query(x*2,l,r)+query(x*2+1,l,r);
    }
}seg;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld %lld %lld %lld",&x1[i],&y1_[i],&x2[i],&y2_[i]);

    for(int i=1;i<=n;i++)tx[2*i-1]=x1[i],tx[2*i]=x2[i];
    sort(tx+1,tx+2*n+1);
    lx=unique(tx+1,tx+2*n+1)-(tx+1);
    for(int i=1;i<=n;i++){
        x1[i]=lower_bound(tx+1,tx+lx+1,x1[i])-tx;
        x2[i]=lower_bound(tx+1,tx+lx+1,x2[i])-tx;
    }

    for(int i=1;i<=n;i++)ty[2*i-1]=y1_[i],ty[2*i]=y2_[i];
    sort(ty+1,ty+2*n+1);
    ly=unique(ty+1,ty+2*n+1)-(ty+1);
    for(int i=1;i<=n;i++){
        up[lower_bound(ty+1,ty+ly+1,y1_[i])-ty].push_back(i);
        dn[lower_bound(ty+1,ty+ly+1,y2_[i])-ty].push_back(i);
    }
    // for(int i=1;i<=ly;i++){
    //     printf("UP:");
    //     for(int j=0;j<(int)up[i].size();j++)printf("%d ",up[i][j]);
    //     printf("\nDN:");
    //     for(int j=0;j<(int)dn[i].size();j++)printf("%d ",dn[i][j]);
    //     printf("\n");
    // }

    seg.build(1,1,lx);
    for(int i=1;i<=ly;i++){
        // printf("%d %lld\n",i,seg.query(1,1,lx));
        // for(int i=1;i<=lx;i++)printf("%lld ",seg.query(1,i,i));
        // printf("\n");
        ans+=seg.query(1,1,lx)*(ty[i]-ty[i-1]);
        for(int j=0;j<(int)dn[i].size();j++)
            seg.update(1,x1[dn[i][j]]+1,x2[dn[i][j]],-1);
        for(int j=0;j<(int)up[i].size();j++)
            seg.update(1,x1[up[i][j]]+1,x2[up[i][j]],1);
    }
    printf("%lld",ans);
    return 0;
}