记录

#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
struct segment{
	int xi,y1,y2,val;
	const bool operator < (const segment &O)const{
		return xi<O.xi;
	}
}s[229028];
struct node{
	int l,r;
	int t,len;
}tr[114514*7];
int x[229028],y[229028];
int w[229028],h[229028];
void build(int p,int l,int r){
	tr[p].l=l;
	tr[p].r=r;
	tr[p].len=0;
	tr[p].t=0;
	if (l==r){
		return ;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void pushup(int p){
	if (tr[p].t)	tr[p].len=y[tr[p].r]-y[tr[p].l-1];
	else	tr[p].len=tr[p*2].len+tr[p*2+1].len;
}
void change(int p,int l,int r,int d){
	if (l<=tr[p].l&&r>=tr[p].r){
		tr[p].t+=d;
		pushup(p);
		return ;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if (l<=mid)	change(p*2,l,r,d);
	if (r>mid)	change(p*2+1,l,r,d);
	pushup(p);
}
signed main(){
	int n,ans=0;
	scanf("%lld",&n);
	int x1,x2,y1,y2;
	for (int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		s[i*2-1]=(segment){x1,y1,y2,1};
		s[i*2]= (segment){x2,y1,y2,-1};
		x[i*2-1]=x1;
		x[i*2] = x2;
		y[i*2-1]=y1;
		y[i*2] = y2;
	}
	sort(s+1,s+2*n+1);
	sort(x+1,x+2*n+1);
	sort(y+1,y+2*n+1);
	int totx=unique(x+1,x+2*n+1)-x-1;
	int toty=unique(y+1,y+2*n+1)-y-1;
	for (int i=1;i<=totx;i++)	w[i]=x[i]-x[i-1];
	for (int i=1;i<=toty;i++)	h[i]=y[i]-y[i-1];
	for (int i=1;i<=totx;i++)	s[i].xi=lower_bound(x+1,x+totx+1,s[i].xi)-x;
	for (int i=1;i<=toty;i++)	s[i].y1=lower_bound(y+1,y+toty+1,s[i].y1)-y;
	for (int i=1;i<=toty;i++)	s[i].y2=lower_bound(y+1,y+toty+1,s[i].y2)-y;
	build(1,1,toty);
	for (int i=1;i<=2*n;i++){
		ans+=(w[i]) * tr[1].len;
		change(1,s[i].y1+1,s[i].y2,s[i].val);
	}
	printf("%lld\n",ans);
	return 0;
}`