扫描线

引入

扫描线一般运用在图形上面，它和它的字面意思十分相似，就是一条线在整个图上扫来扫去，它一般被用来解决图形面积，周长，以及二维数点等问题。

Atlantis 问题

题意

在二维坐标系上，给出多个矩形的左下以及右上坐标，求出所有矩形构成的图形的面积。

解法

根据图片可知总面积可以直接暴力即可求出面积，如果数据大了怎么办？这时就需要讲到 扫描线 算法。

过程

现在假设我们有一根线，从下往上开始扫描：

• 如图所示，我们可以把整个矩形分成如图各个颜色不同的小矩形，那么这个小矩形的高就是我们扫过的距离，那么剩下了一个变量，那就是矩形的长一直在变化。
• 我们的线段树就是为了维护矩形的长，我们给每一个矩形的上下边进行标记，下面的边标记为 1，上面的边标记为 -1，每遇到一个矩形时，我们知道了标记为 1 的边，我们就加进来这一条矩形的长，等到扫描到 -1 时，证明这一条边需要删除，就删去，利用 1 和 -1 可以轻松的到这种状态。
• 还要注意这里的线段树指的并不是线段的一个端点，而指的是一个区间，所以我们要计算的是 \(r+1\) 和 \(r-1\)。
• 需要 离散化。

实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m,k,q;
vector<array<int,4>> e;
int ans=0;
vector<int> vx;
struct info
{
    int minx,mincnt;
};
struct node
{
    info val;
    int tag;
}tr[N*8];
info operator+(const info& a, const info& b)
{
    if(a.minx<b.minx)
        return a;
    else if(b.minx<a.minx) return b;
    else
    {
        //cout<<a.mincnt<<" "<<b.mincnt<<endl;
        return (info){a.minx,a.mincnt+b.mincnt};
    }
}
void update(int p)
{
    tr[p].val=tr[2*p].val+tr[2*p+1].val;
    //cout<<p<<" "<<tr[p].val.mincnt<<endl;
}
void settag(int p,int t)
{
    tr[p].tag+=t;
    tr[p].val.minx+=t;
}
void pushdown(int p)
{
    if(tr[p].tag)
    {
        int t=tr[p].tag;
        settag(2*p,t);
        settag(2*p+1,t);
        tr[p].tag=0;
    }
}
void build(int p,int l,int r)
{
    if(l==r)
    {
        //cout<<vx[r]-vx[r-1]<<endl;
        tr[p].val={0,vx[r]-vx[r-1]};
        tr[p].tag=0;
        return ;
    }
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    update(p);
    //cout<<tr[p].val.mincnt<<endl;
}
void modify(int p,int l,int r,int ql,int qr,int tag)
{
    if(l==ql&&r==qr)
    {
        settag(p,tag);
        return ;
    }
    int mid=(l+r)/2;
    pushdown(p);
    if(qr<=mid) modify(2*p,l,mid,ql,qr,tag);
    else if(ql>mid) modify(2*p+1,mid+1,r,ql,qr,tag);
    else{
        modify(2*p,l,mid,ql,mid,tag);
        modify(2*p+1,mid+1,r,mid+1,qr,tag);
    }
    update(p);
}
info query(int p,int l,int r,int ql,int qr)
{
    if(l==ql&&r==qr)
    {
        return tr[p].val;
    }
    int mid=(l+r)/2;
    pushdown(p);
    if(qr<=mid) return query(2*p,l,mid,ql,qr);
    else if(ql>mid) return query(2*p+1,mid+1,r,ql,qr);
    else return query(2*p,l,mid,ql,mid)+
    query(2*p+1,mid+1,r,mid+1,qr);
    update(p);
}
void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        e.push_back({y1,1,x1,x2});
        e.push_back({y2,-1,x1,x2});
        vx.push_back(x1);
        vx.push_back(x2);
    }
    sort(e.begin(),e.end());
    sort(vx.begin(),vx.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    m=vx.size()-1;
    build(1,1,m);
    //for(int i=1;i<=10;i++) cout<<tr[i].val.mincnt<<" ";
    int s=tr[1].val.mincnt;
    //cout<<s<<endl;
    int pre=0;
    int now=0;
    for(auto et : e)
    {
        int cnt=s;
        now=et[0];
        int d=tr[1].val.minx;
        //cout<<cnt<<endl;
        if(d==0) cnt-=tr[1].val.mincnt;
        ans+=(now-pre)*cnt;
        //cout<<cnt<<endl;
        pre=now;
        int x1=lower_bound(vx.begin(),vx.end(),et[2])-vx.begin()+1;
        int x2=lower_bound(vx.begin(),vx.end(),et[3])-vx.begin();
        //cout<<x1<<" "<<x2<<endl;
        if(x1>x2) continue;
        modify(1,1,m,x1,x2,et[1]);
    }
    cout<<ans<<endl;
    return ;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    T=1;
    //cin>>T;
    while(T--)
     {
         solve();
     }
     return 0;
} 

练习

• 「POJ1151」Atlantis

• 「POJ1177」Picture

• 「POJ3832」Posters

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

B 维正交范围

B 维正交范围指在一个 B 维直角坐标系下，第 \(i\) 维坐标在一个整数范围 \([l_i,r_i]\) 间，内部的点集。

一般来说，一维正交范围简称区间，二维正交范围简称矩形，三维正交范围简称立方体（我们常说的二维数点就是二维正交范围）。

对于一个静态的二维问题，我们可以使用扫描线扫一维，数据结构维护另一维。
在扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询。
如果查询的信息可差分的话直接使用差分，否则需要使用分治。差分一般用树状数组和线段树维护，但因为树状数组好写而且常数小，所以大部分人会选择用树状数组来维护。分治一般是 CDQ 分治（但是这里不涉及分治）。

另一种比较容易理解的看待问题的角度是站在序列角度，而不站在二维平面角度。如果我们这样看待问题，则扫描线实际上是枚举了右端点 \(r=1\cdots n\)，维护一个数据结构，支持查询对于当前的 \(r\)，给定一个值 \(l\)，\(l\) 到 \(r\) 的答案是什么。即扫描线扫询问右端点，数据结构维护所有左端点的答案，或者说遍历一维，数据结果维护另一维。

复杂度一般为 \(O((n+m)\log n)\)。

二维数点

给一个长为 \(n\) 的序列，有 \(m\) 次查询，每次查区间 \([l,r]\) 中值在 \([x,y]\) 内的元素个数。

这个问题就叫做二维数点。我们可以发现等价于我们要查询一个二维平面上矩形内的点的数量和。这里讲一下这个问题最简单的处理方法，扫描线 + 树状数组。

很显然，这个问题是一个静态的二维问题，我们通过扫描线可以将静态的二维问题转换为动态的一维问题。维护动态的一维问题就使用数据结构维护序列，这里可以使用树状数组。

先将所有的询问离散化，用树状数组维护权值，对于每次询问的 \(l\) 和 \(r\)，我们在枚举到 \(l-1\) 时统计当前位于区间 \([x,y]\) 内的数的数量 \(a\)，继续向后枚举，枚举到 \(r\) 时统计当前位于区间 \([x,y]\) 内的数的数量 \(b\)，\(b-a\) 即为该次询问的答案。

例题

洛谷 P2163[SHOI2007] 园丁的烦恼

题意：求\([x1,x2],[y1,y2]\)区间内有多少个点
思路，可以用扫描线+树状数组来做，按y轴从下到上扫描，同是将x坐标离散化，计算一个差分即可得出答案
代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m,k,q;
int a[N];
int c[N];
vector<array<int,4>> event;
int lowbit(int x)
{
    return x&(-x);
}
void modify(int p)
{
    for(;p<=N;p+=lowbit(p))
    {
        c[p]++;
    }
}
int query(int x)
{
    int res=0;
    for(;x>0;x-=lowbit(x))
    {
        res+=c[x];
    }
    return res;
}
vector<int> ans(N+1);
vector<int> vx;
void solve()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        vx.push_back(x);
        event.push_back({y,0,x,i});
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        event.push_back({d,2,c,i});
        event.push_back({d,1,a-1,i});
        event.push_back({b-1,1,c,i});
        event.push_back({b-1,2,a-1,i});
    }
    sort(event.begin(),event.end());
    sort(vx.begin(),vx.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    for(auto ets : event)
    {
        if(ets[1]==0)
        {
            int id=lower_bound(vx.begin(),vx.end(),ets[2])-vx.begin()+1;
            modify(id);
        }
        else
        {
            int id=upper_bound(vx.begin(),vx.end(),ets[2])-vx.begin();
            int s=query(id);
            if(ets[1]==2) ans[ets[3]]+=s;
            else ans[ets[3]]-=s;
        }
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return ;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    T=1;
    //cin>>T;
    while(T--)
     {
         solve();
     }
     return 0;
} 

洛谷 P1908 逆序对

没错，逆序对也可以用扫描线的思维来做。考虑将求逆序对的个数转化为从后向前枚举每个位置 \(i\)，求在区间 \([i+1,n]\) 中，大小在区间 \([0,a_i]\) 中的点的个数。题目中数据范围为 \(10^9\)，很显然要先进行离散化，我们可以考虑从后向前遍历数组，每次遍历到一个数时更新树状数组（线段树），之后统计当前一共有多少个数小于当前枚举的数，因为我们是从后向前遍历的，所以比当前值小的数的个数就是他的逆序对的个数，可以用树状数组或线段树进行单点修改和区间查询。

洛谷 P1972 [SDOI2009] HH 的项链

简要题意：给定一个序列，多次询问区间 \([l,r]\) 中有多少种不同的数。

这类问题我们可以考虑推导性质，之后使用扫描线枚举所有右端点，数据结构维护每个左端点的答案的方法来实现，我们也可以将问题转换到二维平面上，变为一个矩形查询信息的问题。

在本题中，我们设序列中 \(a_i\) 上一次出现的位置为 \(pre_i\)，如果 \(a_i\) 没有出现过，则 \(pre_i = 0\)。根据题意，如果一种数在区间中出现多次，只会产生一次贡献。不妨认为每种数产生贡献的位置是区间中第一次出现的位置，这时可以发现，产生的总贡献即为 \(pre_x \le l - 1\) 的个数，反证法易证。

现在问题即为：给定一个序列 \(pre\)，多次查询区间 \([l,r]\) 中有多少个 \(pre_i \le l - 1\)。

我们可以把 \(pre_i\) 看成二维平面的点：\(i\) 是横坐标，\(pre_i\) 是纵坐标，问题就转化为了二维数点问题：每次询问左下角为 \((l,0)\)，右上角为 \((r,l - 1)\) 的矩形中有几个点。

注意到这个询问是可差分的，我们可以将询问差分为左下角为 \((0,0)\)，右上角为 \((r,l - 1)\) 的矩形减去左下角为 \((0,0)\)，右上角为 \((l - 1,l - 1)\) 的矩形有几个点，这样方便我们使用扫描线思想。

单次操作复杂度 \(O(\log n)\)，共有 \(n\) 次加点操作和 \(2m\) 次查询操作，总时间复杂度 \(O((n + m) \log n)\)。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10,mod=998244353;
typedef long long ll;
typedef pair<int,int> PII;
int T;
int n,m,k,q;
vector<array<int,4>> e;
int c[N];
int a[N];
int pre[N];
int id[N];
int lowbit(int x)
{
  return x&(-x);
}
void modify(int p,int x)
{
  for(;p<=n;p+=lowbit(p))
  {
      c[p]+=x;
  }
}
int query(int x)
{
  int res=0;
  for(;x>0;x-=lowbit(x))
  {
      res+=c[x];
  }
  return res;
}
int ans[N];
void solve()
{
  cin>>n;
  for(int i=1;i<=n;i++)
  {
      cin>>a[i];
      pre[a[i]]=id[a[i]];
      e.push_back({pre[a[i]],0,i,i});
      id[a[i]]=i;
  }
  cin>>q;
  for(int i=1;i<=q;i++)
  {
      int l,r;
      cin>>l>>r;
      e.push_back({l-1,1,r,i});
      e.push_back({l-1,2,l-1,i});
  }
  sort(e.begin(),e.end());
  for(auto et : e)
  {
      if(et[1]==0)
      {
          modify(et[2],1);
      }
      else
      {
          int s=query(et[2]);
          if(et[1]==1) ans[et[3]]+=s;
          else ans[et[3]]-=s;
      }
  }
  for(int i=1;i<=q;i++) cout<<ans[i]<<endl;
  return ;
}
signed main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  T=1;
  //cin>>T;
  while(T--)
   {
       solve();
   }
   return 0;
} 

例题

• 洛谷 P8593「KDOI-02」一个弹的投 逆序对的应用。

• AcWing 4709. 三元组 上题的弱化版，同样为逆序对的应用。

• 洛谷 P8773[蓝桥杯 2022 省 A] 选数异或 HH 的项链魔改版。

• 洛谷 P8844[传智杯 #4 初赛] 小卡与落叶 树上问题转序列问题然后进行二维数点。

总而言之，二维数点的主要思路就是数据结构维护一维，然后枚举另一维。

参考资料

• https://www.cnblogs.com/yangsongyi/p/8378629.html

• https://blog.csdn.net/riba2534/article/details/76851233

• https://blog.csdn.net/winddreams/article/details/38495093

• https://dregen-yor.cf/2022/10/01/sao-miao-xian