扫描线30pts求助
查看原帖
扫描线30pts求助
494601
gcx12012楼主2023/3/14 11:12

不知道哪里错了

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define N 200010

using namespace std;
ll n;
ll xo,yo,xt,yt,X[N<<1];
struct node{
	ll l,r,h,mark;
}line[N<<1];
struct node2{
	ll l,r,sum,len;
}tree[N<<2];

ll read(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
bool cmp1(node x,node y){
	return x.h<y.h;
}
void build(int x,int l,int r){
	tree[x].l=l;
	tree[x].r=r;
	tree[x].len=0;
	tree[x].sum=0;
	if(l==r) return;
	int mid=(l+r)/2;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	return;
}
void pushup(int x){
	int l=tree[x].l;
	int r=tree[x].r;
	if(tree[x].sum) tree[x].len=X[r+1]-X[l];
	else tree[x].len=tree[x<<1].len+tree[x<<1|1].len;
}
void add(ll x,ll L,ll R,ll c){
	int l=tree[x].l;
	int r=tree[x].r;
	if(X[r+1]<=L || R<=X[l]) return;
	if(L<=X[l] && X[r+1]<=R){
		tree[x].sum+=c;
		pushup(x);
		return;
	}
	add(x<<1,L,R,c);
	add(x<<1|1,L,R,c);
	pushup(x);
}

int main()
{
	n=read();
	for(int i=1;i<=n;i++){
		xo=read(),yo=read(),xt=read(),yt=read();
		X[2*i-1]=xo;
		X[2*i]=xt;
		line[2*i-1].l=xo;
		line[2*i-1].r=xt;
		line[2*i-1].h=yo;
		line[2*i-1].mark=1;
		line[2*i].l=xo;
		line[2*i].r=xt;
		line[2*i].h=yt;
		line[2*i].mark=-1;
	}
	n<<=1;
	sort(line+1,line+n+1,cmp1);
	sort(X+1,X+n+1);
	int tot=unique(X+1,X+n+1)-X-1;
	build(1,1,tot-1); 
	ll ans=0;
	for(int i=1;i<n;i++){
		add(1,line[i].l,line[i].r,line[i].mark);
		ans+=tree[1].len*(line[i+1].h-line[i].h);
	}
	cout<<ans;
	return 0;
}
2023/3/14 11:12
加载中...