扫描线

经典问题之求矩形面积并，可以使用线段树和扫描线。

比方说我们要对这俩东西求面积并，我们简单分割一下。

然后扫描线就是，从最下面一条绿线向上扫过去，遇到下底边则加上这个矩形，遇到上底边则减去这个矩形。

回到这道题，发现给了我们矩形的两个角，那么上底边和下底边是好求的。

发现这样对图形分层之后，每部分的高是好求的，就是所有底边排个序两两做差。于是考虑求底的长度。

这几条绿线把 \(x\) 轴分成了 \(5\) 部分，显然 \(1,5\) 两部分没什么用，所以忽略不计。

我们对 \(2,3,4\) 三部分建立线段树，线段树的叶子维护一个区间的线段的信息。

然后我们依次扫过所有边，显然只有 \(2\times n\) 条。

我们对于每个区间维护四个东西，分别是：这个区间在线段树中的下标范围，当前区间被几个矩形完整覆盖，当前区间被覆盖的长度。

这里简单说一下上传：考虑当前矩形是否被完全覆盖。如果是，那么长度直接为这个区间所能达到的最大长度，否则从两个儿子更新。

代码：

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;
int n,x[N<<1];
struct line{
	int l,r,h,flag;
	bool operator<(const line &t)const{
		return h<t.h;
	}
}l[N<<1];
struct node{
	int l,r,sum,len;
	//l,r区间左右端点
	//sum该区间被几个矩形完全覆盖
	//len该区间被覆盖的长度 
}tr[N<<4];
//需要开16倍，因为pushup中会访问到这么大的点，虽然这个点啥也没存 
void pushup(int u){
	int l=tr[u].l,r=tr[u].r;
	if(tr[u].sum!=0)tr[u].len=x[r+1]-x[l];
	//被完全覆盖则不能用子区间更新，因为子节点没有记录信息 
	else tr[u].len=tr[u<<1].len+tr[u<<1|1].len;
}
void build(int u,int l,int r){
	tr[u]={l,r,0,0};
	if(l==r)return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
	//其实pushup没必要，都是0 
}
void modify(int u,int L,int R,int add){
	int l=tr[u].l,r=tr[u].r;
	if(x[r+1]<=L||x[l]>=R)return;
	//完全无交，直接返回 
	if(x[l]>=L&&x[r+1]<=R){
		tr[u].sum+=add;
		pushup(u);
		return; 
		//把这个区间的线加上/删掉 
	}
	modify(u<<1,L,R,add);
	modify(u<<1|1,L,R,add);
	pushup(u);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) {
		int x_1,y_1,x_2,y_2;
		cin>>x_1>>y_1>>x_2>>y_2;
		x[2*i-1]=x_1;x[2*i]=x_2;
		l[2*i-1]={x_1,x_2,y_1,1};
		l[2*i]={x_1,x_2,y_2,-1};
	}
	n<<=1;
	sort(x+1,x+n+1);
	sort(l+1,l+n+1);
	int tot=unique(x+1,x+n+1)-x-1;
	build(1,1,tot-1);
	//这里[l,r]表示x[l]-x[r+1]
	//否则在访问单点时长度为x[l]-x[l]=0，显然不对
	//所以tot-1实际到了x[tot]
	int res=0;
	for(int i=1;i<n;i++){
		modify(1,l[i].l,l[i].r,l[i].flag);
		res+=tr[1].len*(l[i+1].h-l[i].h);
	}
	cout<<res;
	return 0;
}