[求助] 萌新刚学扫描线,#6被hack了,求调
查看原帖
[求助] 萌新刚学扫描线,#6被hack了,求调
533297
Patronus楼主2023/9/17 15:03
#include<bits/stdc++.h>
using namespace std;
#define int long long
int ls(int p){return p<<1;}
int rs(int p){return p<<1|1;}
const int N=2000005;
struct Scanline{//从下往上扫 
	int l,r,h,inout; //下边为1,上边为-1
	Scanline(){}
	Scanline(int a,int b,int c,int d):l(a),r(b),h(c),inout(d) {}
}line[N];
bool cmp(Scanline &a,Scanline &b){return a.h<b.h;}//y坐标排序 
bool lbd[N],rbd[N];//该节点左右两个端点是否被覆盖(0无 1有) 
int num[N];//该区间有多少条独立的边
int Tag[N];//该节点是否有效 
int length[N];//该区间的有效宽度 
void pushup(int p,int pl,int pr){
	if(Tag[p]){  //该线段对计算宽度有效
		lbd[p]=rbd[p]=true;
		length[p]=pr-pl+1;
		num[p]=1;	//每条横边都有两条端点
	}
	else if(pl==pr)
		length[p]=num[p]=lbd[p]=rbd[p]=0;	//叶子节点没有宽度 
	else{
		lbd[p]=lbd[ls(p)];//和左儿子共左端点
		rbd[p]=rbd[rs(p)];//和右儿子共右端点
		length[p]=length[ls(p)]+length[rs(p)];
		num[p]=num[ls(p)]+num[rs(p)];
		if(lbd[rs(p)] && rbd[ls(p)]) num[p]-=1;//合并边 
	}
}
void update(int L,int R,int io,int p,int pl,int pr){
	if(L<=pl && R>=pr){
		Tag[p]+=io;
		pushup(p,pl,pr);
		return;
	}
	int mid=(pl+pr)>>1;
	if(L<=mid) update(L,R,io,ls(p),pl,mid);
	if(R>mid) update(L,R,io,rs(p),mid+1,pr);
	pushup(p,pl,pr);
}
signed main(){
	int n;
	cin>>n;
	int cnt=0,Lbd=1e6,Rbd=-1e6;
	for(int i=1;i<=n;i++){
		int x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2;
		Lbd=min(Lbd,x1);
		Rbd=max(Rbd,x2);
		line[++cnt]=Scanline(x1,x2,y1,1);//入边赋值 
		line[++cnt]=Scanline(x1,x2,y2,-1);//出边赋值 
	}	
	sort(line+1,line+cnt+1,cmp);//对扫描线按y轴方向从低到高排序
	int ans=0,last=0;//last为上一次总区间被覆盖的长度 
	for(int i=1;i<=cnt;i++){	//扫描所有入边和出边 
		if(line[i].l<line[i].r)
			update(line[i].l,line[i].r-1,line[i].inout,1,Lbd,Rbd-1);
		ans+=num[1]*2*(line[i+1].h-line[i].h);//竖线
		ans+=abs(length[1]-last);//横线 
		last=length[1];
	}
	cout<<ans<<endl;
	return 0;
} 
2023/9/17 15:03
加载中...