题解 | #Picture#

思路

线段树扫描线的经典题。求周长并和求面积并是类似的，把横线和竖线分别用结构体记录下来，在横线(扫描线)从下往上扫的同时，通过线段树对竖线进行区间修改，然后得出答案，累加到最终结果。 注意每一次更新操作，都要确认当前高度有多少条线段，是否可以合并为更少的线段。 每次答案的贡献是扫描线高度差×竖线条数+扫描线长度

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

struct E{
	int l,r,h,f;
	bool operator <(const E &a)const{ //扫描线按高度排序 
		return h<a.h;
	}
}e[N];

struct Node{ //线段树 
	int l,r,len,s,num; //分别为结点左右端点、区间长度、合并标记和线段个数 
	bool lc,rc; //左右儿子合并标记 
}tr[N<<2];

#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((tr[p].l+tr[p].r)>>1)

void pushup(int p){ //向上合并 
	if(tr[p].s){
		tr[p].len=tr[p].r-tr[p].l+1;
		tr[p].lc=tr[p].rc=1;
		tr[p].num=1;
	}else{
		tr[p].len=tr[ls].len+tr[rs].len;
		tr[p].lc=tr[ls].lc;
		tr[p].rc=tr[rs].rc;
		tr[p].num=tr[ls].num+tr[rs].num-(tr[ls].rc&tr[rs].lc);
	}
}

void build(int p,int l,int r){ //建树 
	tr[p].l=l;tr[p].r=r;
	if(l==r) return;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
 
void update(int p,int ql,int qr,int k){ //区间修改 
	if(ql==tr[p].l&&qr==tr[p].r){
		tr[p].s+=k;
		pushup(p);
		return;
	}
	if(qr<=mid) update(ls,ql,qr,k);
	else if(ql>mid) update(rs,ql,qr,k);
	else update(ls,ql,mid,k),update(rs,mid+1,qr,k);
	pushup(p);
} 

signed main(){
	int n;
	while(cin>>n){
		int x1,x2,y1,y2,mx=-inf,mi=inf;
		int tot=0;
		for(int i=0;i<n;i++){
			cin>>x1>>y1>>x2>>y2;
			mx=max(mx,max(x1,x2));
			mi=min(mi,min(x1,x2));
			e[tot++]=(E){x1,x2,y1,1};
			e[tot++]=(E){x1,x2,y2,-1};
		}
		sort(e,e+tot);
		int ans=0,lst=0;
		build(1,mi,mx-1);
		for(int i=0;i<tot;i++){
			update(1,e[i].l,e[i].r-1,e[i].f);
			ans+=abs(tr[1].len-lst);
			ans+=(e[i+1].h-e[i].h)*2*tr[1].num;
			lst=tr[1].len;
		}
		cout<<ans<<"\n";
	}
	return 0;
}