扫描线-526互联

#include<bits/stdc++.h>
#define maxn 200005
#define int long long
using namespace std;
int x[maxn];//x[i]表示从左往右第i条竖边
int tsum[maxn<<3],tlen[maxn<<3];
//tsum表示当前节点被覆盖的次数
//tlen是当前节点所对应的长方形的长 

void pushup(int k,int l,int r)//tsum是由+1-1决定的，所以只更新tlen 
{
	if(tsum[k]) tlen[k] = x[r+1]-x[l];
	//若整个区间都被访问过了则tlen为对应的区间长度
	else tlen[k] = tlen[k<<1]+tlen[k<<1|1];
	//否则为左右节点的长方形长之和 
}

struct node{
	int l,r,h,v;
}y[maxn];

bool cmp(node x, node y)
{
	return x.h<y.h;
}

void updata(int k,int l,int r,int L,int R,int v)
{
	//LR指的是实际区间而不是x的下标
	//lr指的是x的实际下标范围 
	if(L <=x[l] && x[r+1]<=R)//如果在区间内就直接更新tsum
	{
		tsum[k] += v;
		pushup(k,l,r);//更新tlen，因为tlen也是受tsum影响的 
		return;
	} 
	int m = l + ((r-l)>>1);
	if(l < x[m+1])
		updata(k<<1,l,m,L,R,v);
	//与一般的线段树不同，更新[1,3],不用更新[3,4]这个区间，故不用取等
	//时刻注意区间[l,m]对应x的范围是[l,m+1]
	if(R>x[m+1])
		updata(k << 1 | 1, m + 1, r, L, R, v);
	pushup(k,l,r);
		 
}

signed main()
{
	int n;
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		//先纵坐标后横坐标 
		x[2*i-1] = x1;
		x[2*i] = x2;
		y[2*i-1] = {x1,x2,y1,1};
		y[2*i] = {x1,x2,y2,-1};
	}
	sort(y+1,y+1+2*n,cmp);
	sort(x+1,x+1+2*n);
	int len = unique(x+1,x+1+2*n)-x-1,ans = 0;//去重 
	for(int i = 1;i <2*n;i++)
	{
		updata(1,1,len-1,y[i].l,y[i].r,y[i].v);
		//len-1因为对应的是“左端点” 
		ans+=tlen[1]*(y[i+1].h-y[i].h);
		//宽度是下一条边高度减去当前高度 
	}
	cout<<ans;
	return 0;
}