扫描线求周长

样例输出284

在线求助

真的查不出来了

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=10010;
int n,X[N]; 
struct pos{
	int l,r,h,val;
	bool operator < (const pos &k) const {
		if(h==k.h) return val>k.val;
		return h<k.h;
	}
}mat[N];
struct qaq{
	int l,r,fl,cl,cr;
	LL len,sum; 
}t[N<<3];
void pushup(int rt){
	int l=t[rt].l,r=t[rt].r;
	if(t[rt].fl){
		t[rt].sum=t[rt].cl=t[rt].cr=1;
		t[rt].len=X[r+1]-X[l];
	}
	else{
		t[rt].len=t[rt<<1].len+t[rt<<1|1].len;
		t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;
		t[rt].cl=t[rt<<1].cl;t[rt].cr=t[rt<<1|1].cr;
		if(t[rt<<1].cr&&t[rt<<1|1].cl) t[rt].sum--;
	}
}
void build(int rt,int l,int r){
	t[rt].l=l;t[rt].r=r;
	t[rt].len=t[rt].fl=t[rt].cl=t[rt].cr=0;
	if(l==r) return;
	int mid=l+r>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
}
void update(int rt,int L,int R,int fl){
	int l=t[rt].l,r=t[rt].r;
	if(X[r+1]<=L||R<=X[l]) return;
	if(L<=X[l]&&X[r+1]<=R){
		t[rt].fl+=fl;
		pushup(rt);
		return;
	} 
	update(rt<<1,L,R,fl);
	update(rt<<1|1,L,R,fl);
	pushup(rt);
}
int main(){
	LL ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int xa,xb,ya,yb;
		scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
		X[(i<<1)-1]=xa;X[i<<1]=xb;
		mat[(i<<1)-1]=(pos){xa,xb,ya,1};
		mat[i<<1]=(pos){xa,xb,yb,-1};
	}
	n<<=1;
	sort(mat,mat+n+1);
	sort(X+1,X+n+1);
	int tot=unique(X+1,X+n+1)-X-1;
	build(1,1,tot-1);
	LL last=0;
	for(int i=1;i<n;i++){
		update(1,mat[i].l,mat[i].r,mat[i].val);
		ans+=2*t[1].sum*(mat[i+1].h-mat[i].h);
		ans+=abs(t[1].len-last);
		last=t[1].len;
	}
	ans+=mat[n].r-mat[n].l;
	printf("%lld\n",ans);
	return 0;
}