假设有一条扫描线从一个图形的下方扫向上方（或者左方扫到右方），那么通过分析扫描线被图形截得的线段就能获得所要的结果。该过程可以用线段树进行加速。
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在
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;
}