扫描线

假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用线段树进行加速。
P5490 【模板】扫描线
扫描线可以处理两类问题
一类是面积并
一类是周长并

#include<iostream>
#include<algorithm>
using namespace std;
#define ls u<<1
#define rs u<<1|1
typedef long long ll;
const int N = 2e5+10;
struct line{
	int x1,x2,y;//每一条扫描线的左右端点及其纵坐标
	int tag;//入边为1，出边为-1
	bool operator<(line &t){
		return y<t.y;
	}
}L[N<<1];//每个矩阵会产生两条扫描线
struct tree{
	int l,r;
	ll cnt,len;
	//  cnt: 被完全覆盖的次数；
	//  len: 区间内被截的长度。
}tr[N<<3];
int X[N<<1];
void build(int u,int l,int r){
	tr[u]={l,r,0,0};
	if(l==r)return;
	int mid = (l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
void pushup(int u){
	int l=tr[u].l,r=tr[u].r;
	if(tr[u].cnt)//      更新长度
		tr[u].len= X[r+1]-X[l];
	else //      合并儿子信息
		tr[u].len=tr[ls].len+tr[rs].len;
}
void modify(int u,int l,int r,int tag){
	if(l>tr[u].r||r<tr[u].l)return;
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].cnt+=tag;
		pushup(u);
		return;
	}
	modify(ls,l,r,tag);
	modify(rs,l,r,tag);
	pushup(u);
}
int x1,x2,y1,y2;
int main(){
	int n;
	scanf("%d",&n);
	
	for(int i=1;i<=n;i++){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		L[i]={x1,x2,y1,1};
		L[n+i]={x1,x2,y2,-1};
		X[i]=x1,X[n+i]=x2;
	}
	n*=2;
	sort(L+1,L+n+1);
	sort(X+1,X+n+1);
	int tot = unique(X+1,X+n+1)-X-1;//去重 
	//tot为离散化后有多少个节点  
	build(1,1,tot-1);
	ll ans=0;
	for(int i=1;i<n;i++){
		int l = lower_bound(X+1,X+tot+1,L[i].x1)-X;
		int r = lower_bound(X+1,X+tot+1,L[i].x2)-X;
		modify(1,l,r-1,L[i].tag);
		ans+=1ll*tr[1].len*(L[i+1].y-L[i].y);
	}	
	
	printf("%lld",ans);
	return 0;	
} 

注意：变量名y1在库里头有定义，会冲突，所以不开bits库就好。

P1856 [IOI1998] [USACO5.5] 矩形周长Picture

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+10;
struct Line{
	int l,r,y;
	int tag;//入边：1 ;出边：-1 
	bool operator<(Line &t){
		return y==t.y? tag>t.tag:y<t.y;
	}
}L[N*2];
int X[N*2];
struct tree{
	int l,r;
	int cnt,len;//区间覆盖次数和覆盖长度 
	int sum;//区间覆盖的竖边条数 
	bool lcover,rcover;//左右端点是否被覆盖，用于线段树的区间合并
}tr[N*8];
void build(int u,int l,int r){
	tr[u]={l,r,0,0,0,0,0};
	if(l==r){
		
		return;
	}
	int mid = (l+r)/2;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void pushup(int u){
	int l = tr[u].l,r=tr[u].r;
	if(tr[u].cnt){
		tr[u].len = X[r+1]-X[l];
		tr[u].sum = 2;
		tr[u].lcover = tr[u].rcover = true;
	}
	else{
		tr[u].len = tr[u<<1].len+tr[u<<1|1].len;
		tr[u].sum = tr[u<<1].sum+tr[u<<1|1].sum;
		tr[u].lcover = tr[u<<1].lcover;
		tr[u].rcover = tr[u<<1|1].rcover;
		if(tr[u<<1|1].lcover&&tr[u<<1].rcover)
			tr[u].sum -= 2;//左右区间连续 
	} 
}
void modify(int u,int l,int r,int tag){
	if(l>tr[u].r||tr[u].l>r)return;
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].cnt+=tag;
		pushup(u);
		return;
	}
	
	modify(u<<1,l,r,tag);
	modify(u<<1|1,l,r,tag);
	pushup(u);
}
int x1,x2,y1,y2,pre;
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		X[i] = x1;X[i+n] = x2;
		L[i]={x1,x2,y1,1};
		L[n+i]={x1,x2,y2,-1};
	}
	n*=2;
	sort(L+1,L+n+1);
	sort(X+1,X+n+1);
	int tot = unique(X+1,X+n+1)-X-1;//统计可以离散化为多少个点
	int res = 0;
	build(1,1,tot-1);
	for(int i=1;i<n;i++){
		int l = lower_bound(X+1,X+tot+1,L[i].l)-X;
		int r = lower_bound(X+1,X+tot+1,L[i].r)-X;
		
		modify(1,l,r-1,L[i].tag);
		res+=abs(tr[1].len-pre);//计算横边 
		pre=tr[1].len;
		res+=tr[1].sum*(L[i+1].y-L[i].y);//计算竖边 
	}
	res+=L[n].r-L[n].l;//加上最后一条扫描线的长度。
	printf("%d",res);
	return 0; 
}