P5490 扫描线

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e5+7;
int n;
struct L{
	ll x,x2,y;
	int w;
}a[N<<1];
ll z[N<<1];
bool cmp(L a,L b){
	return a.y!=b.y?a.y>b.y:a.w>b.w;   
}
ll tr[N<<2],tr2[N<<2]; 
void add(int p,int l,int r,int x,int y,int w){
	if(x<=l&&r<=y){
		tr[p]+=w;
		if(tr[p]>0) tr2[p]=z[r+1]-z[l];
		else {
			tr2[p]=tr2[p*2]+tr2[p*2+1];
		}
		return ;
	}
	int mid=(l+r) >> 1;
	if(x<=mid) add(p*2,l,mid,x,y,w);
	if(mid+1<=y) add(p*2+1,mid+1,r,x,y,w);
	if(tr[p]>0) tr2[p]=z[r+1]-z[l];
	else {
		tr2[p]=tr2[p*2]+tr2[p*2+1];
	}
}

int main(){
	cin >> n;
	for(int i=1;i<=n;++i){
		cin >> a[i].x >> a[i].y >> a[i].x2 >> a[i+n].y;
		a[i+n].x=a[i].x;a[i+n].x2=a[i].x2;
		a[i].w=-1;a[i+n].w=1;  
		z[i]=a[i].x;z[i+n]=a[i].x2;
	}
	n<<=1;
	sort(z+1,z+n+1);
	sort(a+1,a+n+1,cmp);
	int cnt=unique(z+1,z+n+1)-z-1;
	for(int i=1;i<=n;++i){
		a[i].x=lower_bound(z+1,z+n+1,a[i].x)-z;
		a[i].x2=lower_bound(z+1,z+n+1,a[i].x2)-z;
	}
	ll ans=0,res;
	add(1,1,n,a[1].x,a[1].x2-1,a[1].w);  // 
	for(int i=2;i<=n;++i){
		ans+=tr2[1]*(a[i-1].y-a[i].y);
		add(1,1,n,a[i].x,a[i].x2-1,a[i].w);
	}
	cout << ans;
	return 0;	
}