扫描线-线段树

求面积并

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=1e6+10;
int n;

int X[N*2];
struct segment
{
	int l,r,h,val;
}seg[N*2];

bool cmp(segment a,segment b)
{
	return a.h<b.h;
}

struct tree
{
	int l,r;
	int val;
	int len;
#define l(x) t[x].l
#define r(x) t[x].r
#define val(x) t[x].val
#define len(x) t[x].len
}t[N*4];

void pushup(int p)
{
	if(val(p)) len(p)=X[r(p)+1]-X[l(p)];
	else len(p)=len(p<<1)+len(p<<1|1);
}

void build(int p,int l,int r)
{
	l(p)=l,r(p)=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}

void update(int p,int l,int r,int val)
{
	if(l>=X[r(p)+1]||r<=X[l(p)]) return;
	if(l<=X[l(p)]&&r>=X[r(p)+1])
	{
		val(p)+=val;
		pushup(p);
		return;
	}
	update(p<<1,l,r,val);
	update(p<<1|1,l,r,val);
	pushup(p);
}

int main(){
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		X[2*i-1]=a,X[2*i]=c;
		seg[2*i-1]={a,c,b,1};
		seg[2*i]={a,c,d,-1};
	}
	n<<=1;
	sort(seg+1,seg+1+n,cmp);
	sort(X+1,X+1+n);
	int len=unique(X+1,X+1+n)-X-1;
	
	build(1,1,len-1);
	
	LL ans=0;
	for(int i=1;i<n;i++)
	{
		update(1,seg[i].l,seg[i].r,seg[i].val);
		ans+=(LL)len(1)*(LL)(seg[i+1].h-seg[i].h);
	}
	printf("%lld",ans);
	
	return 0;
}

求周长

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e4+10;
int n;

int X[N*2];
struct segment
{
	int l,r,h,val;
}seg[N];

bool cmp(segment a,segment b)
{
	if(a.h==b.h) return a.val>b.val;
	return a.h<b.h;
}

struct tree
{
	int l,r;
	int cov;
	int lc,rc;
	int val;
	int len;
	int cnt;
	
#define l(x) t[x].l
#define r(x) t[x].r
#define cov(x) t[x].cov
#define lc(x) t[x].lc
#define rc(x) t[x].rc
#define val(x) t[x].val
#define len(x) t[x].len
#define cnt(x) t[x].cnt
	
}t[N*4];

void pushup(int p)
{
	if(cov(p))
	{
		lc(p)=rc(p)=1;
		len(p)=X[r(p)+1]-X[l(p)];
		cnt(p)=1;
	}
	else 
	{
		len(p)=len(p<<1)+len(p<<1|1);
		lc(p)=lc(p<<1),rc(p)=rc(p<<1|1);
		cnt(p)=cnt(p<<1)+cnt(p<<1|1);
		if(rc(p<<1)&&lc(p<<1|1)) cnt(p)--;
	}
}

void build(int p,int l,int r)
{
	l(p)=l,r(p)=r;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
}
void update(int p,int l,int r,int val)
{
	if(l>=X[r(p)+1]||r<=X[l(p)]) return;
	if(l<=X[l(p)]&&r>=X[r(p)+1])
	{
		cov(p)+=val;
		pushup(p);
		return;
	}
	update(p<<1,l,r,val);
	update(p<<1|1,l,r,val);
	pushup(p);
}

int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		seg[2*i-1]={a,c,b,1};
		seg[2*i]={a,c,d,-1};
		X[2*i-1]=a;
		X[2*i]=c;
	}
	
	n<<=1;
	sort(seg+1,seg+1+n,cmp);
	sort(X+1,X+1+n);
	int len=unique(X+1,X+1+n)-X-1;
	build(1,1,len-1);
	
	LL ans=0;
	int p=0;
	for(int i=1;i<n;i++)
	{
		update(1,seg[i].l,seg[i].r,seg[i].val);
		ans+=(LL)abs(p-len(1));
		ans+=(LL)2*cnt(1)*(LL)(seg[i+1].h-seg[i].h);
		p=len(1);
	}
	ans+=(LL)seg[n].r-seg[n].l;
	printf("%lld",ans);
	
	return 0;
}