扫描线
cpp
struct Line{
int l,r,h,tag;
bool operator<(const Line&tmp)const{
return h<tmp.h;
}
};
struct Node{
int l,r,len,tag;
} t[N<<3];
vector<int> nums;
void pushup(int p){
if(t[p].tag){
t[p].len=nums[t[p].r+1]-nums[t[p].l];
return;
}
if(t[p].l!=t[p].r)t[p].len=t[p<<1].len+t[p<<1|1].len;
else t[p].len=0;
}
void build(int p,int l,int r){
t[p]={l,r,0,0};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int x){
if(nums[t[p].r+1]<=r&&nums[t[p].l]>=l){
t[p].tag+=x;
pushup(p);
return;
}
if(nums[t[p].r+1]<=l||nums[t[p].l]>=r)return;
modify(p<<1,l,r,x);
modify(p<<1|1,l,r,x);
pushup(p);
}
void solve(){
int n;
cin>>n;
vector<Line> line;
for(int i=1;i<=n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
line.push_back({a,c,b,1});
line.push_back({a,c,d,-1});
nums.push_back(a);
nums.push_back(c);
}
sort(line.begin(),line.end());
sort(nums.begin(),nums.end());
nums.erase(unique(nums.begin(),nums.end()),nums.end());
build(1,0,nums.size()-2);
ll ans=0;
for(int i=0;i<line.size()-1;i++){
auto [l,r,h,tag]=line[i];
modify(1,l,r,tag);
ans+=1ll*t[1].len*(line[i+1].h-h);
}
cout<<ans<<"\n";
}