题解：P8648 [蓝桥杯 2017 省 A] 油漆面积

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int n,X[N<<1];
struct node{
	int l,r,h,mk;
	bool operator<(const node&oth)const{
		return h<oth.h;
	}
}li[N<<1];
struct Node{
	int l,r,len,sum;
}hv[N<<2];
inline void fun1(int id){
	if(hv[id].sum)hv[id].len=X[hv[id].r+1]-X[hv[id].l];
	else hv[id].len=hv[(id<<1)].len+hv[(id<<1|1)].len; 
}
void fun2(int id,int l,int r){
	hv[id].l=l,hv[id].r=r;
	hv[id].len=hv[id].sum=0;
	if(l>=r)return;
	int mid=(l+r)>>1;
	fun2((id<<1),l,mid);
	fun2((id<<1|1),mid+1,r);
}
void add(int id,int L,int R,int mrk){
	int l=hv[id].l,r=hv[id].r;
	if(X[l]>=R||X[r+1]<=L)return;
	if(X[l]>=L&&X[r+1]<=R){
		hv[id].sum+=mrk;
		fun1(id);
		return;
	}
	add((id<<1),L,R,mrk);
	add((id<<1|1),L,R,mrk);
	fun1(id);
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x1_,x2_,y1_,y2_;
		cin>>x1_>>y1_>>x2_>>y2_;
		X[2*i-1]=x1_,X[i<<1]=x2_;
		li[2*i-1]=(node){x1_,x2_,y1_,1};
		li[i<<1]=(node){x1_,x2_,y2_,-1};
	}
	n<<=1;
	sort(X+1,X+n+1);
	sort(li+1,li+n+1);
	int tot=unique(X+1,X+n+1)-X-1;
	fun2(1,1,tot-1);
	int ans=0;
	for(int i=1;i<n;i++){
		add(1,li[i].l,li[i].r,li[i].mk);
		ans+=hv[1].len*(li[i+1].h-li[i].h);
	}
	cout<<ans;
	return 0;
}