首页 > 其他分享 >扫描线

扫描线

时间：2024-08-27 19:37:42浏览次数：12  
标签：int back push 扫描线 vx 矩形

引入

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

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;
}

练习

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;
}

例题

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

参考资料

标签：int,back,push,扫描线,vx,矩形
From： https://www.cnblogs.com/prioritymygirl/p/18383366

相关文章

  • 扫描线
    扫描线经典问题之求矩形面积并，可以使用线段树和扫描线。比方说我们要对这俩东西求面积并，我们简单分割一下。然后扫描线就是，从最下面一条绿线向上扫过去，遇到下底边则加上这个矩形，遇到上底边则减去这个矩形。回到这道题，发现给了我们矩形的两个角，那么上底边和下底边是好求的。......
  • 扫描线总结
    扫描线是线段树的典型应用。这玩意不难，用途也比较狭窄，重点在理解思想。例0【模板】扫描线题意求\(n\)个四边平行于坐标轴的矩形的面积并。对于\(100\%\)的数据，\(1\len\le{10}^5\)，\(0\lex_1<x_2\le{10}^9\)，\(0\ley_1<y_2\le{10}^9\)。解析如果用暴力......
  • 刍议线段树 3 （扫描线）
    扫描线扫描线是一种另外的思想，只是其中会运用到线段树以求优化。所以不要将扫描线简单的并为线段树的一个小拓展。例题：https://www.luogu.com.cn/problem/P5490大意：求\(n\)个四边平行于坐标轴的矩形的面积并。思路：纵向分割图形我们考虑把这些纵向矩形分割。那么，总面积就......
  • 扫描线
    Abstract介绍一下扫描线的经典用法。命名空间还挺好用的。A-扫描线（模板）Idea想象现在有一根线正在从左向右扫描，那么，我们就可以通过纵坐标上区间的覆盖情况去确定扫过的矩形覆盖的面积,区间覆盖情况可以用线段树去维护。实现细节见代码注释。Code#include<bits/stdc++.h>#......
  • 扫描线学习笔记
    前言扫描线思想可以在\(O(n^2)\)的时间复杂度内进行二维平面的计算，运用线段树优化可以在\(O(n\logn)\)的时间复杂度内解决。简介P5490【模板】扫描线以此题为例，介绍扫描线。最直接的想法是将每个正方形的面积先加起来，最后再减去重叠部分，但是代码难度较大，不易于实现。......
  • 扫描线学习笔记
    扫描线是一种算法思想，其特征为将静态\(k\)维问题转化为动态\(k-1\)维问题。动态\(k-1\)维问题往往需要数据结构维护。例题【模板】扫描线题意：求矩形面积并，其中每个举行的四边平行于坐标轴。考虑扫描线，将静态\(2\)维问题转化为动态\(1\)维问题。具体的，考虑按\(......
  • 算法随笔——扫描线
    https://www.acwing.com/solution/content/135911/放个模板先P5490【模板】扫描线#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineINF0x3f3f3f3f#definereregister#defineintll#definePIIpair<int,int>intread(){ intf=1,k=0......
  • Cesium雷达扫描线效果
    更多精彩内容尽在dt.sim3d.cn，关注公众号【sky的数孪技术】，技术交流、源码下载请添加VX：digital_twin123源码如下：varviewer=newCesium.Viewer("cesiumContainer");varscene=viewer.scene;varmatGLSL="#defineLlength(c-.1*......
  • 扫描线
    扫描线把题目给的的区间想象成平面直角坐标系上的点.再想象一条直线,按顺序扫描获取信息,维护信息求出矩形面积并:把一个矩形看出两条平行于纵轴的边,一条表示加入,一条表示删除,有很多区间的信息是一样的,用乘法处理,扫描线上的信息最多变动\(2n\)次考虑用线段树......
  • [University CodeSprint 4] Drawing Rectangles （扫描线 + 最小点覆盖）
    [UniversityCodeSprint4]DrawingRectangles扫描线+最小点覆盖题目的形式一看就是扫描线，观察到矩形的并面积\(\le3\times10^5\)，所以可以直接把这些位置找出来。这部分的复杂度是\(O(n\logn)\)。然后剩下的部分就是一个经典的最小点覆盖问题。具体的说，构造二分图，左边代......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99