扫描线18求调,哪位大佬能帮帮忙
查看原帖
扫描线18求调,哪位大佬能帮帮忙
779484
c2105cxy楼主2024/9/20 16:46
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
#define int long long
struct segline{
	long long h,l,r,mark;
}line[4*N];
bool cmp(segline a,segline b){
	return a.h<b.h;
}
long long x[4*N];
struct tree{
	long long l,r,sum;
	long long len;
}tr[8*N];
void pushup(int p){
	if(tr[p].sum){
		tr[p].len=x[tr[p].r+1]-x[tr[p].l];
		return;
	}
	if(tr[p].l==tr[p].r){
		tr[p].len=0;
		return;
	}
	tr[p].len=tr[p*2].len+tr[p*2+1].len;
}
void build(int p,int l,int r){
	tr[p].l=l;
	tr[p].r=r;
	tr[p].sum=tr[p].len=0;
	if(l==r)return;
	int mid=l+r>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
}
void add(int p,int ll,int rr,int k){
	if(tr[p].l>=ll&&tr[p].r<=rr){
		tr[p].sum+=k;
		pushup(p);
		return;
	}
	int mid=tr[p].l+tr[p].r>>1;
	if(mid>=ll)add(p*2,ll,rr,k);
	if(mid+1<=rr)add(p*2+1,ll,rr,k);
	pushup(p);
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		x[i*2-1]=x1;
		x[i*2]=x2;
		line[i*2-1]={y1,x1,x2,1};
		line[i*2]={y2,x1,x2,-1};
	}
	n*=2;
	sort(line+1,line+1+n,cmp);
	sort(x+1,x+1+n);
	int tot=unique(x+1,x+1+n)-x-1;
	build(1,1,tot-1);
	long long ans=0;
	for(int i=1;i<n;i++){
		int l=lower_bound(x+1,x+1+n,line[i].l)-x;
		int r=lower_bound(x+1,x+1+n,line[i].r)-x;
		add(1,l,r-1,line[i].mark);
		ans+=(line[i+1].h-line[i].h)*tr[1].len;
	}
	cout<<ans;
	return 0;
}
2024/9/20 16:46
加载中...