原题链接

题解

把覆盖的区域变成黑色，然后在区域内划几条竖线，一定能分成若干个矩形左右拼接而成的图形

想象一条竖着的线，它的运动轨迹是不连续的，即他会从一个矩形的竖边跳到另一个矩形的竖边，每跳一条竖边都会对借着竖边归属的矩形的信息对这条竖边的激活块进行修改
当竖线的绝对位置发生移动时，计算激活区间产生的面积

所以哪些信息需要被记录？
1.每个矩形的左右两个竖边
2.矩形对其左右两竖边的修改信息
3.y的区间块，以计算激活长度

code

#define ll long long
#include<bits/stdc++.h>
using namespace std;
struct unit
{
    ll x,y1,y2,op;
}segch[4000005];

bool cmp(unit a,unit b)
{
    return a.x<b.x;
}

ll y[4000005]={0};

struct
{
    ll sit,val;
}tree[10000008];

void pushup(ll node)//有点类似于单点修改，区间查询
{
    tree[node].val=tree[node*2].val+tree[node*2+1].val;
}

void change(ll node,ll down,ll up,ll y1,ll y2,ll op)
{
    if(y1<down||y2>up) return ;

    if(y1>=up&&y2<=down)
    {
        tree[node].sit+=op;//代表区间是否整个被激活
        if(tree[node].sit)
        {
            tree[node].val=y[up+1]-y[down];
        }
        else
        {
            tree[node].val=0;
            pushup(node);
        }
        return ;
    }

    ll mid=(up+down)>>1;
    change(node*2,down,mid,y1,y2,op);
    change(node*2+1,mid+1,up,y1,y2,op);
    if(!tree[node].sit)pushup(node);//必须要判断，因为只有没有被完整激活的情况下才能启用子节点，不然完整激活被覆盖了
}

inline void read(ll &x) {
    x = 0;
    ll flag = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')flag = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    x *= flag;
}

inline void write(ll x)
{
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}

int main()
{
    ll n;
    read(n);
    for(ll i=1;i<=n;i++)
    {
        ll x1,y1,x2,y2;
        read(x1); read(y1); read(x2); read(y2);
        if(x1>x2)swap(x1,x2);
        if(y1<y2)swap(y1,y2);

        segch[2*i-1]={x1,y1,y2,1};//代表需要修改的区间块，x代表当竖线遍历到x时他才会发动修改
        segch[2*i]={x2,y1,y2,-1};

        y[2*i-1]=y1;
        y[2*i]=y2;
    }

    n*=2;

    sort(y+1,y+1+n);
    ll len=unique(y+1,y+n+1)-y-1;//这两步其实都是为了方便拿取每个矩形对其竖边的修改信息

    sort(segch+1,segch+1+n,cmp);//这个是为了能够找出突兀变化竖边以计算区域面积

    ll ans=0;
    for(ll i=1;i<n;i++)//遍历所有的修改信息
    {
        ll y1=lower_bound(y+1,y+len+1,segch[i].y1)-y;
        ll y2=lower_bound(y+1,y+len+1,segch[i].y2)-y;//找出当前修改信息要修改的区域块

        change(1,1,len-1,y1-1,y2,segch[i].op);//对当前竖线做区间修改
        if(segch[i+1].x>segch[i].x) ans+=(segch[i+1].x-segch[i].x)*tree[1].val;//tree是实时的竖线激活区间长度
    }

    write(ans);
    putchar('\n');
    return 0;
}