准备学习扫描线的时候，发现洛谷日报上并没有关于扫描线的文章，于是心血来潮想写一篇。顺便纪念一下我马上结束的 OI 生涯。
前置知识
-
线段树或树状数组 （不会的请【模板】线段树 1 ，【模板】树状数组 1 )
-
离散化
目的
先来了解一下扫描线都能做些什么：
-
矩形面积并
-
矩形周长问题
-
二维数点（静态区间查询类问题）
-
B 维正交范围
正文
先讲一讲矩形面积并相关问题
先来看一道例题：P5490 【模板】扫描线。
题意：给定 \(n\) 个矩形，求这 \(n\) 个矩形的并集覆盖的总面积。
众所周知，矩形的面积等于长乘宽，根据这个性质，我们考虑以纵轴为底建立一颗线段树，维护当前的截线段长度，并在枚举下一个点时统计答案，更新截线段长度。可以看成在模拟一条直线，这条直线不断地向右运动，并在移动的时候记录他扫过的矩形面积。
以下面这张图为例：
我们从左向右扫，先扫到下面的位置：
这时候用线段树更新一下目前线段覆盖的范围，然后继续向右扫。
扫描到这个位置时，我们需要将刚才扫过的面积记录到答案中，即上次覆盖的区间范围 \(\times\) 移动的距离。并用线段树更新当前覆盖范围，然后继续向右扫描。
每次线段的覆盖面积发生变化时都将当前通过的面积计入答案中，然后用线段树更新现在线段覆盖的区域大小。
重复上述步骤即可。
因为题目中数据范围是 \(10^9\)，所以要把矩形的坐标离散化。这时这道题基本上已经解决了。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
ll x,y0,y1,c;
}a[200001];
ll n,m,book[4000000],L[8000010],R[8000010],len[8000001],v[8000010];
ll ans;
map <ll,ll> sum;
bool cmp(node a,node b){
return a.x<b.x;
}
void bulid(ll x,ll l,ll r){
L[x]=l;
R[x]=r;
if(l==r){
return;
}
ll mid=l+r >>1;
bulid(x<<1,l,mid);
bulid(x<<1|1,mid+1,r);
}
void updata(ll x,ll l,ll r,ll data){
if(r<L[x]||l>R[x]){
return;
}
if(L[x]>=l&&R[x]<=r){
v[x]+=data;
}else{
updata(x<<1,l,r,data);
updata(x<<1|1,l,r,data);
}
if(v[x])len[x]=book[R[x]+1]-book[L[x]];//减去重复覆盖的部分
else len[x]=len[x<<1]+len[x<<1|1];
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x0,y0,x1,y1;
scanf("%d%d%d%d",&x0,&y0,&x1,&y1);
a[i]=node{x0,y0,y1,1};
a[i+n]=node{x1,y0,y1,-1};
book[++m]=y1;
book[++m]=y0;
}
sort(book+1,book+1+m);
m=unique(book+1,book+m+1)-book-1;//离散化
for(int i=1;i<=m;i++){
sum[book[i]]=i;
}
n<<=1;
bulid(1,1,n);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
updata(1,sum[a[i].y0],sum[a[i].y1]-1,a[i].c);
ans+=(ll)len[1]*(a[i+1].x-a[i].x);
}
cout<<ans;
return 0;
}
再来看一个计算矩形周长并的例题：P1856 [IOI1998] [USACO5.5] 矩形周长Picture。
把面积换成周长后这道题毒瘤了十倍。
由于第一篇题解的图画的太好了，我就不献丑了，可以直接看第一篇题解的图。
通过观察题目所给图片以及第一篇题解图片，我们不难发现：纵边总长度 \(=\sum2\times\) 被截得的线段条数 \(\times\) 当前扫过的高度。
横边总长度 \(=\sum|\)上次截得的总长 \(-\) 现在截得的总长 \(|\)。
横边总长度也可以用求纵边总长度相同的方法再求一遍。
和面积并相比，周长并中还要维护线段的个数，而且横边和纵边需要分开计算。
由于这题数据比较水，所以不需要离散化，但要注意点的坐标存在负数的情况。
代码如下:
#include<bits/stdc++.h>
#define rg register
using namespace std;
const int MAXN=5010;
const int MAXM=20010;
const int INF=2147483647;
inline int read(){
int s=0;bool f=false;char c=getchar();
while(c<'0'||c>'9')f|=(c=='-'),c=getchar();
while(c>='0'&&c<='9')s=(s<<3)+(s<<1)+(c^48),c=getchar();
return (f)?(-s):(s);
}
struct node{
int l,r,cnt;
int numx,numy;
bool lf,rf;
}c[MAXM<<2];
#define lson rt<<1
#define rson rt<<1|1
inline void pushup(int rt){
if(c[rt].cnt){
c[rt].numx=c[rt].r-c[rt].l+1;
c[rt].lf=c[rt].rf=true;
c[rt].numy=1;
}
else if(c[rt].l==c[rt].r){
c[rt].numx=0;
c[rt].numy=0;
c[rt].lf=c[rt].rf=false;
}
else{
c[rt].numx=c[lson].numx+c[rson].numx;
c[rt].lf=c[lson].lf;
c[rt].rf=c[rson].rf;
c[rt].numy=c[lson].numy+c[rson].numy-(c[lson].rf&c[rson].lf);
}
}
inline void build(int rt,int l,int r){
c[rt].l=l;
c[rt].r=r;
c[rt].cnt=0;
c[rt].numx=0;
c[rt].numy=0;
c[rt].lf=false;
c[rt].rf=false;
if(l==r) return;
int mid=(l+r)>>1;
build(lson,l,mid);
build(rson,mid+1,r);
}
inline void update(int rt,int l,int r,int v){
if(l<=c[rt].l&&c[rt].r<=r)
return c[rt].cnt+=v,pushup(rt);
int mid=(c[rt].l+c[rt].r)>>1;
if(l<=mid)update(lson,l,r,v);
if(r>mid) update(rson,l,r,v);
pushup(rt);
}
struct edge{int l,r,h,f;}e[MAXN<<1];
bool cmp(edge a,edge b){
return a.h<b.h||(a.h==b.h&&a.f>b.f);
}
int main(){
int n=read(),tot=0;
int maxl=INF,maxr=-INF;
for(rg int i=1;i<=n;i++){
int x1=read(),y1=read();
int x2=read(),y2=read();
maxl=min(maxl,min(x1,x2));
maxr=max(maxr,max(x1,x2));
e[++tot]=(edge){x1,x2,y1,1};
e[++tot]=(edge){x1,x2,y2,-1};
}
sort(e+1,e+tot+1,cmp);
long long ans=0,last=0;
build(1,maxl,maxr-1);
for(rg int i=1;i<=tot;i++){
update(1,e[i].l,e[i].r-1,e[i].f);
ans+=labs(c[1].numx-last);
ans+=(e[i+1].h-e[i].h)*2*c[1].numy;
last=c[1].numx;
}
printf("%lld\n",ans);
return 0;
}
说说 B 维正交范围
B 维正交范围指在一个 B 维直角坐标系下，第 \(i\) 维坐标在一个整数范围 \([l_i,r_i]\) 间，内部的点集。
一般来说，一维正交范围简称区间，二维正交范围简称矩形，三维正交范围简称立方体。（后面提到的二维数点就是二维正交范围）
对于一个静态的二维问题，我们可以使用扫描线扫一维，数据结构维护另一维。
在扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询。
如果查询的信息可差分的话直接使用差分，否则需要使用分治。差分一般用树状数组和线段树维护，但因为树状数组好写而且常数小，所以大部分人会选择用树状数组来维护。分治一般是 CDQ 分治（蒟蒻不会CDQ 分治，所以这里不涉及）。
另一种比较容易理解的看待问题的角度是站在序列角度，而不站在二维平面角度。如果我们这样看待问题，则扫描线实际上是枚举了右端点 \(r=1\cdots n\)，维护一个数据结构，支持查询对于当前的 \(r\)，给定一个值 \(l\)，\(l\) 到 \(r\) 的答案是什么。即扫描线扫询问右端点，数据结构维护所有左端点的答案。
复杂度一般为 \(\mathcal O((n+m)\log n)\)。
来看几道例题吧。
口胡例题
给一个长为 \(n\) 的序列，有 \(m\) 次查询，每次查区间 \([l,r]\) 中值在\([x,y]\) 内的元素个数。
这个问题就叫做二维数点。我们可以发现等价于我们要查询一个二维平面上矩形内的点的数量和。这里讲一下这个问题最简单的处理方法，扫描线+树状数组。
很显然，这个问题是一个静态的二维问题，我们通过扫描线可以将静态的二维问题转换为动态的一维问题。
维护动态的一维问题就使用数据结构维护序列，这里可以使用树状数组。
先将所有的询问离散化，用树状数组维护权值，对于每次询问的 \(l\) 和 \(r\)，我们在枚举到 \(l-1\) 时统计当前位于区间 \([x,y]\) 内的数的数量 \(a\)，继续向后枚举，枚举到 \(r\) 时统计当前位于区间 \([x,y]\) 内的数的数量 \(b\)，\(b-a\) 即为该次询问的答案。
可以用我的这道题进行练习。
P1908 逆序对。
没错，逆序对也可以用扫描线的思维来做。考虑将求逆序对的个数转化为从后向前枚举每个位置 \(i\)，求在区间 \([i+1,n]\) 中，大小在区间 \([0,a_i]\) 中的点的个数。题目中数据范围为 \(10^9\)，很显然要先进行离散化，我们可以考虑从后向前遍历数组，每次遍历到一个数时更新数组数组（线段树），之后统计当前一共有多少个数小于当前枚举的数，因为我们是从后向前遍历的，所以比当前值小的数的个数就是他的逆序对的个数，可以用树状数组或线段树进行单点修改和区间查询。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
ll data;
ll num;
}f[5000001];
ll n,c[5000001],ans,a[5000001];
bool cmp(node a,node b){
if(a.data==b.data){
return a.num<b.num;
}
return a.data<b.data;
}
inline ll lowbit(ll i){
return i&(-i);
}
inline ll sum(ll x){
ll s=0;
for(;x>0;x-=lowbit(x)){
s+=c[x];
}
return s;
}
int main(){
cin>>n;
for(ll i=1;i<=n;i++){
cin>>f[i].data;
f[i].num=i;
}
sort(f+1,f+1+n,cmp);
for(int i=1;i<=n;i++){
a[f[i].num]=i;
}
for(ll i=n;i>0;i--){
ans+=sum(a[i]);
for(ll j=a[i];j<=n;j+=lowbit(j)){
c[j]++;
}
}
cout<<ans;
return 0;
}
P1972 [SDOI2009] HH的项链
简要题意：给定一个长为 \(n\) 的序列，\(m\) 次查询区间中有多少不同的数。
这类问题我们可以考虑推导性质，之后使用扫描线枚举所有右端点，数据结构维护每个左端点的答案的方法来实现，我们也可以将问题转换到二维平面上，变为一个矩形查询信息的问题。
在这道题中，对于每个位置 \(i\)，考虑预处理出 \(i\) 左边离 \(i\) 最近的 \(j\) 满足 \(a_i=a_j\)，用一个数组记录，即 \(pre_i=j\)。
然后查询区间中的不同数，我们可以只把每个数在区间中最后一次出现时统计进去。
若这个数在当前区间中是第一次出现，那么这个数肯定满足 \(pre_i<l\)。如果不是第一次出现，那么 \(l \le pre_i\)。这样问题就转变成了求区间 \([l,r]\) 中，满足 \(pre_i<l\) 的 \(i\) 的个数。
我们可以考虑差分，将区间 \([l,r]\) 差分为前缀 \([1,r]\) 减去前缀 \([1,l-1]\)。考虑将询问离线处理，假设有一个询问是对于区间 \([l,r]\) 的，我们在 \(l-1\) 位置上和 \(r\) 位置上分别记录一下，答案为在 \(r\) 处记录的 \(pre_i<l\) 的个数减去在 \(l-1\) 处记录的 \(pre_i<l\) 的 \(i\) 的个数。
每次查询可以用值域线段树或值域树状数组来维护，注意一个位置上可能有多个询问，但总共的查询次数是 \(m\) 次。总时间复杂度 \(\mathcal O((n+m)\log n)\)。
代码如下：
#include <bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
#define N 1000010
using namespace std;
struct node{
int l,r,ans;
}q[N];
struct t{
int num,s;
};
vector <t> p[N];
int n,a[N],m,now[N];
int siz[N<<2];
void update(int x,int l,int r,int ad){
if(l==r&&l==ad){
siz[x]++;
return;
}
int mid=l+r>>1;
if(ad<=mid){
update(ls,l,mid,ad);
}
else{
update(rs,mid+1,r,ad);
}
siz[x]=siz[ls]+siz[rs];
}
int query(int x,int l,int r,int L,int R){
if(l>=L&&r<=R){
return siz[x];
}
int mid=l+r>>1;
int res=0;
if(L<=mid){
res+=query(ls,l,mid,L,R);
}
if(R>mid){
res+=query(rs,mid+1,r,L,R);
}
return res;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
p[l-1].push_back(t{i,-1});
p[r].push_back(t{i,1});
q[i]=node{l,r,0};
}
for(int i=1;i<=n;i++){
update(1,0,n,now[a[i]]);
now[a[i]]=i;
for(auto x:p[i]){
int num=x.num;
q[num].ans+=x.s*query(1,0,n,0,q[num].l-1);
}
}
for(int i=1;i<=m;i++){
printf("%d\n",q[i].ans);
}
return 0;
}
完结撒花。
萌新第一次写日报，如有错误，希望各位大佬及时指正。
参考资料：
【学习笔记】扫描线 by NCC79601。
扫描线模型 by nzhtl1477。
标签：浅谈,int,线段,数组,扫描线,矩形,ll From： https://www.cnblogs.com/Dregen-Yor/p/16705131.html