「USACO5.5」矩形周长Picture

「USACO5.5」矩形周长Picture

求所有矩形合并后的周长

开两个线段树，一个从左往右扫，另外一个从下往上扫

当扫描线扫到蓝色的线段时，相对于上次需要增加，当前覆盖的长度为红色线段，而相对于上一次，我们增加的值为绿色线段长度，然后我们可以发现绿色线段的长度，是红色线段的长度减去橙色线段的长度，也就是这一次的长度减去上一次的长度

当扫描线扫到蓝色的线段时，相对于上次需要增加，但是覆盖长度需要减小，当前操作完之后，覆盖长度是红色线段，而答案需要增加的是绿色线段，也就是橙色线段的长度减去红色线段的长度

总和来看，我们每次遇到一个边界时，操作完成当次操作后，需要答案增加的就是 \(|now-last|\)，然后上下也是同理

但是有一个地方需要注意，我们发现这里的两个边界重合了，这里我们需要先加后减，正确性按照以上所说模拟可以得出，如果反了过来，可以发现中间那个小线段被多算了两次

#include<bits/stdc++.h>
using namespace std;
struct rectangle{
	int x,y1,y2,pos;
}a1[10001],a2[10001];
struct tree{
	int cnt,len;
}t1[40001],t2[40001];
int n,m1,m2,r1[10001],r2[10001];
bool cmp(rectangle u,rectangle v){
	if(u.x==v.x) return u.pos>v.pos;
	else return u.x<v.x;
}
void push_up1(int rt,int l,int r){
	if(t1[rt].cnt>0) t1[rt].len=r1[r+1]-r1[l];
	else if(l==r) t1[rt].len=0;
	else t1[rt].len=t1[rt*2].len+t1[rt*2+1].len;
}
void push_up2(int rt,int l,int r){
	if(t2[rt].cnt>0) t2[rt].len=r2[r+1]-r2[l];
	else if(l==r) t2[rt].len=0;
	else t2[rt].len=t2[rt*2].len+t2[rt*2+1].len;
}
void updata1(int rt,int l,int r,int L,int R,int val){
	if(L<=l&&r<=R){
		t1[rt].cnt+=val;
		push_up1(rt,l,r);
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid) updata1(rt*2,l,mid,L,R,val);
	if(R>mid) updata1(rt*2+1,mid+1,r,L,R,val);
	push_up1(rt,l,r);
}
void updata2(int rt,int l,int r,int L,int R,int val){
	if(L<=l&&r<=R){
		t2[rt].cnt+=val;
		push_up2(rt,l,r);
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid) updata2(rt*2,l,mid,L,R,val);
	if(R>mid) updata2(rt*2+1,mid+1,r,L,R,val);
	push_up2(rt,l,r);
}
int main(){
	long long ans=0,x1,y1,x2,y2,last1=0,last2=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
		a1[i*2-1]={x1,y1,y2,1};
		a1[i*2]={x2,y1,y2,-1};
		a2[i*2-1]={y1,x1,x2,1};
		a2[i*2]={y2,x1,x2,-1};
		r1[i*2-1]=y1;
		r1[i*2]=y2;
		r2[i*2-1]=x1;
		r2[i*2]=x2;
	}
	sort(a1+1,a1+1+n*2,cmp);
	sort(a2+1,a2+1+n*2,cmp);
	sort(r1+1,r1+1+n*2);
	sort(r2+1,r2+1+n*2);
	m1=unique(r1+1,r1+1+n*2)-r1-1;
	m2=unique(r2+1,r2+1+n*2)-r2-1;
	for(int i=1;i<=n*2;i++){
		updata1(1,1,m1,lower_bound(r1+1,r1+1+m1,a1[i].y1)-r1,lower_bound(r1+1,r1+1+m1,a1[i].y2)-r1-1,a1[i].pos);
		updata2(1,1,m2,lower_bound(r2+1,r2+1+m2,a2[i].y1)-r2,lower_bound(r2+1,r2+1+m2,a2[i].y2)-r2-1,a2[i].pos);
		ans+=abs(t1[1].len-last1)+abs(t2[1].len-last2);
		last1=t1[1].len;
		last2=t2[1].len;
	}
	printf("%lld",ans);
	return 0;
}