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