记录编号	576031	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	矩形多次覆盖的面积	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.648 s
提交时间	2022-10-01 11:04:01	内存使用	6.88 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=30000+5;
struct sdf{
	int px,l,r,sgn;
	bool operator<(const sdf&x)const{
		return px<x.px;
	}
}q[2*N];
int n;
int bb[2*N],cnt=0,tot=0; 
struct {
	int l,r,cnt,len1,len2;
}tr[8*N];
void build(int pt,int l,int r){
	tr[pt]={l,r,0,0,0};
	if (l==r)return ;
	int mid=(l+r)/2;
	build(pt*2,l,mid);build(pt*2+1,mid+1,r);
	return ;
}
void update(int pt){
	if (tr[pt].cnt>=2){
		tr[pt].len2=tr[pt].len1=bb[tr[pt].r+1]-bb[tr[pt].l];
	}
	else if (tr[pt].cnt==1){
		if (tr[pt].l==tr[pt].r)tr[pt].len2=0;
		else tr[pt].len2=tr[pt*2].len1+tr[pt*2+1].len1;
		tr[pt].len1=bb[tr[pt].r+1]-bb[tr[pt].l];
	}
	else if (tr[pt].l==tr[pt].r){
		tr[pt].len1=tr[pt].len2=0;
	}
	else{
		tr[pt].len2=tr[pt*2].len2+tr[pt*2+1].len2;
		tr[pt].len1=tr[pt*2].len1+tr[pt*2+1].len1;	
	}
	return ;
}
void change(int pt,int x,int y,int sgn){
	int l=tr[pt].l,r=tr[pt].r;
	if (x<=l&&r<=y){
		tr[pt].cnt+=sgn;update(pt);
		return ;
	}
	int mid=(l+r)/2;
	if (x<=mid)change(pt*2,x,y,sgn);
	if (mid+1<=y)change(pt*2+1,x,y,sgn);
	update(pt);
	return ;
}
int main(){
	freopen ("jxfgmj.in","r",stdin);
	freopen ("jxfgmj.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);cnt=0;
		for (int i=1;i<=n;i++){
			int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d);
			q[++cnt]={a,b,d,1};bb[cnt]=b;
			q[++cnt]={c,b,d,-1};bb[cnt]=d;
		}
		sort(bb+1,bb+cnt+1);sort(q+1,q+2*n+1);
		tot=unique(bb+1,bb+cnt+1)-bb-1;
		for (int i=1;i<=2*n;i++){
			q[i].l=lower_bound(bb+1,bb+tot+1,q[i].l)-bb;
			q[i].r=lower_bound(bb+1,bb+tot+1,q[i].r)-bb;
		}
		build(1,1,tot-1);
		long long ans=0;
		for (int i=1;i<2*n;i++){
			change(1,q[i].l,q[i].r-1,q[i].sgn);
			ans+=1ll*(q[i+1].px-q[i].px)*tr[1].len2;
		}
		printf("%lld\n",ans);
	}
	return 0;
}