0分求调
查看原帖
0分求调
1268529
jiangbaolin楼主2025/1/22 18:00
#include<bits/stdc++.h>
using namespace std;
long long n,x,x2,y,y2,k[5500001],p1,p2,l,f[5500001],mx=-0x7fffffff,s1;
struct st{
	int a,b,c,d;
}s[5500001];
struct tree{
	int l,r,len,c;
}t[5500001];
bool cmp(st a,st b){
	if(a.a!=b.a){
		return a.a<b.a;
	}
	return a.d>b.d;
}
void build(int p,int l,int r){
	t[p].l=l;
	t[p].r=r;
	if(r==l){
		return;
	}
	long long m=(t[p].l+t[p].r)/2;
	build(p<<1,l,m);
	build(p<<1|1,m+1,r);
}
void change(int p,int l,int r,int s){
	if(l<=t[p].l&&t[p].r<=r){
		t[p].c=t[p].c+s;
		if (t[p].l==mx && t[p].r==mx){
			return;
		}
		if (t[p].c){
			t[p].len=f[t[p].r+1]-f[t[p].l];
		}
		else{
			t[p].len=t[p<<1].len+t[p<<1|1].len;
		}
		return;
	} 
	long long m=(t[p].l+t[p].r)/2;
	if(l<=m){
		change(p<<1,l,r,s);
	}
	if(m<r){
		change(p<<1|1,l,r,s);
	}
	if (t[p].l==mx && t[p].r==mx){
		return;
	}
	if (t[p].c){
		t[p].len=f[t[p].r+1]-f[t[p].l];
	}
	else{
		t[p].len=t[p<<1].len+t[p<<1|1].len;
	}
}
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> x >> y >> x2 >> y2;
		s[(i<<1)-1].a=x;
		s[i<<1].a=x2;
		s[(i<<1)-1].b=s[i<<1].b=y2;
		s[(i<<1)-1].c=s[i<<1].c=y;
		s[(i<<1)-1].d=1;
		s[i<<1].d=-1;
		k[++l]=y;
		k[++l]=y2;
	}
	sort(k+1,k+(n<<1)+1);
	l=unique(k+1,k+(n<<1)+1)-k-1;
	for(int i=1;i<=n*2;i++){
		p1=lower_bound(k+1,k+l+1,s[i].b)-k;
		p2=lower_bound(k+1,k+l+1,s[i].c)-k;
		f[p1]=s[i].b;
		f[p2]=s[i].c;
		s[i].b=p1;
		s[i].c=p2;
		mx=max(mx,p1);
	}
	sort(s+1,s+2*n+1,cmp);
	build(1,1,n<<1);
	for(int i=1;i<(1<<n);i++){
		change(1,s[i].c, s[i].b-1, s[i].d);
		s1=s1+t[1].len*(s[i+1].a-s[i].a);
	}
	cout << s1;
	return 0;
}
2025/1/22 18:00
加载中...