萌新刚学扫描线,要调爆炸了,样例未过
查看原帖
萌新刚学扫描线,要调爆炸了,样例未过
546681
lcbridgeAK CSP-S楼主2023/7/11 09:05
#include <bits/stdc++.h>
#define int long long
#define MAXN 1000005
using namespace std;
int n,cnt,ans,xl[MAXN*2];
struct line{
	int x,xx,y,k;
}a[MAXN*2]; 
struct segment{
	int l,r,len,flag;
}t[MAXN*4];
bool cmp(line A,line B){
	return A.y<B.y;
}
void pushup(int x){
	if(t[x].flag)t[x].len=t[x].r-t[x].l;
	else t[x].len=t[x*2].len+t[x*2+1].len;
}
void change(int x,int l,int r,int k){
	int L=t[x].l,R=t[x].r;
	if(R<l||L>r)return ;
	if(l<=L&&R<=r){
		t[x].flag+=k;
		pushup(x);
		return ;
	}
	change(x*2,l,r,k);
	change(x*2+1,l,r,k);
	pushup(x);
}
void build(int x,int l,int r){
	t[x].l=l,t[x].r=r;
	t[x].len=0;
	t[x].flag=0;
	if(l==r)return ;
	int mid=(l+r)/2;
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
}
int query(int x){
	return lower_bound(xl+1,xl+n+1,x)-xl;
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int x,y,xx,yy;
		scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
		xl[i*2-1]=x,xl[i*2]=xx;
		a[i*2-1]=(line){x,xx,y,1},a[i*2]=(line){x,xx,yy,-1};
	}                
	n*=2;            
	sort(a+1,a+n+1,cmp);
	sort(xl+1,xl+n+1); 
	int cnt1=unique(xl+1,xl+n+1)-xl-1;
	build(1,1,cnt1); 
	for(int i=1;i<=n;i++){
		change(1,query(a[i].x),query(a[i].xx)-1,a[i].k);
		ans+=(a[i+1].y-a[i].y)*t[1].len;
		//cout<<t[1].len<<endl;
	}                
	printf("%lld",ans);
	return 0;         
}                    
2023/7/11 09:05
加载中...