扫描线

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=1e7+110;
//line数组是2n所以M要开4n，因为我懒，直接开了1e7 
//快读 
int read(){
	int sum=0,k=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-') k=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		sum=sum*10+c-'0';
		c=getchar();
	} return sum*k;
}
//线段树
//lz 左端点
//rz 右端点
//len 该区间长度
//mark 区间被覆盖次数 
struct nodetree{
	int lz,rz,len,mark;
}t[M];
//扫描线
//lz rz 左右端点
//hz 该扫描线与底部的距离
//mark 该边的位置（上 -1 or 下 1） 
struct nodeline{
	int lz,rz,hz,mark;
}line[M];
//按扫描线的高度进行排序 
bool cmp(nodeline a,nodeline b){
	return a.hz<b.hz;
}
//Li 是离散化数组 Li（离） 
int n,Li[M],ans=0;
//建树 
void build(int id,int l,int r){
	t[id].lz=l,t[id].rz=r;
	if(l==r) return;
	int mid=l+r>>1;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
}
//更新 
void pushup(int id){
	//若被覆盖 该区间长为自己左右端点之差 
	if(t[id].mark) t[id].len=Li[t[id].rz+1]-Li[t[id].lz];
	//区间长为左右儿子区间长之和 
	else t[id].len=t[id<<1].len+t[id<<1|1].len;
}
//id 当前区间编号 
//l,r 要修改的大区间
//val 该扫描线是上还是下-----(ps:其实就是 1 or -1) 
void xiu(int id,int l,int r,int val){
	int ll=t[id].lz,rr=t[id].rz;
	//ll,rr 该区间的长度为ll~rr （ps：方便写，不然就是一大串） 
	if(Li[ll]>=r||Li[rr+1]<=l) return;
	//该区间的最左边比我要修改的最右边还大
	//该区间的最右边比我要修改的最左边还小
	//故舍去 
	if(Li[ll]>=l&&Li[rr+1]<=r) t[id].mark+=val;
	//该区间完全在我要修改的区间中，加加 （更新覆盖情况） 
	else xiu(id<<1,l,r,val),xiu(id<<1|1,l,r,val);
	//递归修改————我在上面已经判断了超界 
	pushup(id);
	//更新 
}
signed main(){
	n=read();
	for(int i=1;i<=n;i++){
		int x1=read(),y1=read(),x2=read(),y2=read();
		//读入 
		Li[i*2-1]=x1,Li[i*2]=x2;
		//离散化数组存了两个值 
		line[i*2-1]=(nodeline){x1,x2,y1,1};
		//下方边 
		line[i*2]=(nodeline){x1,x2,y2,-1};
		//上方边 
		//结构体数组这么写可以直接存 
		//结构体数组名[]=(结构体名){依次是你定义的成员} 
	}   
	n*=2;
	//存了两倍的结构体，一共有2n个数 
	sort(line+1,line+1+n,cmp);
	sort(Li+1,Li+n+1);
	//排序---（os：不会重载运算符，只好写cmp了 55~） 
	int tot=unique(Li+1,Li+1+n)-Li-1;
	//去重，tot为去重后数组中数的数量多少 
	build(1,1,tot-1);
	//建树 
	for(int i=1;i<n;i++){
		//line[i]表示i~i+1这个区间值，故最大为n-1~n，i枚举1~n-1 
		xiu(1,line[i].lz,line[i].rz,line[i].mark);
		//找到此时宽度t[1].len 
		ans+=t[1].len*(line[i+1].hz-line[i].hz);
		//长*宽为该段面积
		//ans累加面积 
	}
	cout<<ans<<endl;
	//输出 
}
/*
2
100 100 200 200
150 150 250 255
*/

求关QWQ