C++(g++ 7.5.0) 解法, 执行用时: 316ms, 内存消耗: 8456K, 提交时间: 2022-09-23 20:11:30

#include<cstdio>
#include<cstring>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int M=3e5+10;
struct segment{
	int segType;
	int yl,yu,x;
	segment(){}
	segment(int a,int b,int c,int d):x(a),yl(b),yu(c),segType(d){}
	bool operator <(const segment &a)const{
		return x<a.x;
	}
}S[M];
int tot,n;
int aa,bb,cc,dd;
int lsh[M],top;
int coverTimes[M<<2],addv[M<<2];
void calc(int o,int l,int r){
	if(coverTimes[o]){
		addv[o]=lsh[r+1]-lsh[l];
	}else{
		if(l==r){
			addv[o]=0;
		}else{
			addv[o]=addv[o<<1]+addv[o<<1|1];
		}
	}
}
void update(int o,int l,int r,int L,int R,int flag){
	if(L<=l&&r<=R){
		coverTimes[o]+=flag;
		calc(o,l,r);
		return;
	}
	int mid=(l+r)>>1;
	if(L<=mid) update(o<<1,l,mid,L,R,flag);
	if(R>mid) update(o<<1|1,mid+1,r,L,R,flag);
	calc(o,l,r);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d%d",&aa,&bb,&cc,&dd);
		S[++tot]=segment(aa,bb,dd,1);
		S[++tot]=segment(cc,bb,dd,-1);
		lsh[++top]=bb;
		lsh[++top]=dd;
	}
	sort(S+1,S+tot+1);
	sort(lsh+1,lsh+top+1);
	int nowtop=1;
	for(int i=2;i<=top;i++){
		if(lsh[nowtop]!=lsh[i]){
			lsh[++nowtop]=lsh[i];
		}
	}
	top=nowtop;
	nowtop=1;
	ll ans=0;
	while(nowtop<=tot){
		int nowx=S[nowtop].x;
		while(nowx==S[nowtop].x){
			int L=lower_bound(lsh+1,lsh+top+1,S[nowtop].yl)-lsh;
			int R=lower_bound(lsh+1,lsh+top+1,S[nowtop].yu)-lsh;
			if(L==R) continue;
			update(1,1,top-1,L,R-1,S[nowtop].segType);
			++nowtop;
		}
		if(nowtop>tot) break;
		ans+=1ll*(S[nowtop].x-nowx)*addv[1];
	}
	printf("%lld\n",ans);
	return 0;
}

C++ 解法, 执行用时: 883ms, 内存消耗: 30700K, 提交时间: 2022-07-20 21:11:03

#include<iostream>
#include<map>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10;
struct Edge 
{
	ll x1,x2;
	ll h;
	ll cnt;
	Edge() {}
	Edge(ll a,ll b,ll c,ll d):x1(a),x2(b),h(c),cnt(d) {}
	bool operator<(const Edge b)
	{
		return h<b.h;
	}
}e[N];
ll px[2*N];
map<ll,ll> idx;
ll lp[N];
struct Node
{
	ll s;
	ll cnt;
}node[N*8];
void update(ll x,ll l,ll r)
{
	if(node[x].cnt) node[x].s=lp[r]-lp[l-1];
	else node[x].s=node[x<<1].s+node[(x<<1)|1].s;
}
void add(ll x,ll l,ll r,ll nl,ll nr,ll k)
{
	if(l<=nl&&r>=nr)
	{
		node[x].cnt+=k;update(x,nl,nr);return ;
	}
	ll mid=(nl+nr)>>1;
	if(mid>=l) add(x<<1,l,r,nl,mid,k);
	if(mid<r) add((x<<1)|1,l,r,mid+1,nr,k);
	update(x,nl,nr);
}
int main()
{
	ll x1,x2,y1,y2;
	ll n;
	ll tot=0;
	cin>>n;
	for(ll i=1;i<=n;i++)
	{
		cin>>x1>>y1>>x2>>y2;
		e[++tot]=Edge(x1,x2,y1,1);
		e[++tot]=Edge(x1,x2,y2,-1);
		px[2*i-1]=x1;px[2*i]=x2;
	}
	sort(px+1,px+2*n+1);
	sort(e+1,e+2*n+1);
	ll m=unique(px+1,px+2*n+1)-px-1;
	for(ll i=1;i<=m;i++) idx[px[i]]=i;
	for(ll i=1;i<m;i++) lp[i]=px[i+1]-px[1];
	ll ans=0;
	for(ll i=1;i<=2*n-1;i++)
	{
		add(1,idx[e[i].x1],idx[e[i].x2]-1,1,m-1,e[i].cnt);
		ans+=node[1].s*(e[i+1].h-e[i].h);
	}
	cout<<ans<<endl;
	return 0;
}