Location>code7788 >text

scanning line

Popularity：398 ℃/2024-08-28 00:49:58

pull into

The scanning line is generally used on top of graphs, and it is very similar to its literal meaning, which is that a line is swept around the entire graph, and it is generally used to solve problems such as area of a graph, perimeter, and counting points in two dimensions.

Atlantis issue

meaning of a title

On a two-dimensional coordinate system, given the lower left as well as upper right coordinates of multiple rectangles, find the area of the figure formed by all the rectangles.

solution (a math problem)

According to the picture can be known as the total area can be directly violent can be derived from the area, if the data is large how to do? At this point it is necessary to talk aboutscanning line Algorithm.

course of events

Now let's say we have a line that starts scanning from the bottom up:

  • As shown in the figure, we can divide the whole rectangle into small rectangles of different colors as shown in the figure, then the height of this small rectangle is the distance we swept, then there is one variable left, that is, the length of the rectangle has been changing.
  • Our line tree is to maintain the length of the rectangle, we mark the upper and lower edges of each rectangle, the lower edge is marked as 1, the upper edge is marked as -1, every time we encounter a rectangle, we know the edge marked as 1, we add in the length of this rectangle, and wait until the scanning of the -1, proving that this edge needs to be deleted, it is deleted, the use of the 1 and -1 can be easily to this state.
  • Note also that the line tree here refers not to an endpoint of a line segment, but to an interval, so we have to compute the\(r+1\) cap (a poem)\(r-1\)。
  • needdiscretization。

realization

#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(<)
        return a;
    else if(<) return b;
    else
    {
        //cout<<<<" "<<<<endl;
        return (info){,+};
    }
}
void update(int p)
{
    tr[p].val=tr[2*p].val+tr[2*p+1].val;
    //cout<<p<<" "<<tr[p].<<endl;
}
void settag(int p,int t)
{
    tr[p].tag+=t;
    tr[p].+=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].<<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((),());
    sort((),());
    (unique((),()),());
    m=()-1;
    build(1,1,m);
    //for(int i=1;i<=10;i++) cout<<tr[i].<<" ";
    int s=tr[1].;
    //cout<<s<<endl;
    int pre=0;
    int now=0;
    for(auto et : e)
    {
        int cnt=s;
        now=et[0];
        int d=tr[1].;
        //cout<<cnt<<endl;
        if(d==0) cnt-=tr[1].;
        ans+=(now-pre)*cnt;
        //cout<<cnt<<endl;
        pre=now;
        int x1=lower_bound((),(),et[2])-()+1;
        int x2=lower_bound((),(),et[3])-();
        //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),(0),(0);
    T=1;
    //cin>>T;
    while(T--)
     {
         solve();
     }
     return 0;
}

practice

  • 「POJ1151」Atlantis

  • 「POJ1177」Picture

  • 「POJ3832」Posters

  • Rock Valley P1856 [IOI1998] [USACO5.5] Rectangular Perimeter Picture

B-dimensional orthogonal range

B-dimensional orthogonal range means that in a B-dimensional right-angled coordinate system the first\(i\) Dimensional coordinates in a range of integers\([l_i,r_i]\) Between, internal point sets.

In general, one-dimensional orthogonal ranges are referred to as intervals, two-dimensional orthogonal ranges are referred to as rectangles, and three-dimensional orthogonal ranges are referred to as cubes (we often refer to two-dimensional numbered points as two-dimensional orthogonal ranges).

For a static two-dimensional problem, we can use scan lines to sweep one dimension and data structures to maintain the other.
As the scan line sweeps from left to right, it generates some modifications and queries on the dimension where the data structure is maintained.
If the query information can be differentiated then directly use the difference, otherwise you need to use the partition. Differentials are generally maintained using tree arrays and line segment trees, but since tree arrays are easy to write and have small constants, most people will choose to maintain them using tree arrays. Partitioning is generally CDQ partitioning (but partitioning is not covered here).

Another, more understandable, way to look at the problem is from a sequence perspective, not from a two-dimensional plane perspective. If we look at the problem this way, the scan line actually enumerates the right endpoints\(r=1\cdots n\), maintains a data structure that supports queries for the current\(r\)Given a value\(l\)，\(l\) until (a time)\(r\) What is the answer to the question. That is, the scan line sweep asks for the right endpoint and the data structure maintains the answers for all the left endpoints, or traverses one dimension and the data result maintains the other dimension.

The complexity is typically\(O((n+m)\log n)\)。

two-dimensional point

Give an object of length\(n\) The sequence with\(m\) Sub-queries, each query interval\([l,r]\) The median value is at\([x,y]\) The number of elements within the

This problem is called counting points in two dimensions. We can find the equivalent in that we want to query the sum of the number of points in a rectangle on a two-dimensional plane. Here is the simplest way to handle this problem, scanlines + tree arrays.

Obviously, this problem is a static two dimensional problem, we can convert a static two dimensional problem to a dynamic one dimensional problem by scanning the line. Maintaining a dynamic one-dimensional problem uses a data structure to maintain the sequence, here you can use a tree array.

First, all queries are discretized and the weights are maintained in a tree array, for each query the\(l\) cap (a poem)\(r\)We are enumerating to\(l-1\) When the statistic is currently in the interval\([x,y]\) Number of numbers within\(a\)The enumeration continues backward to\(r\) When the statistic is currently in the interval\([x,y]\) Number of numbers within\(b\)，\(b-a\) is the answer to that query.

example

Rock Valley P2163 [SHOI2007] The Gardener's Trouble

Problem: Find\([x1,x2],[y1,y2]\)How many points in the range
Idea, you can use the scan line + tree array to do, according to the y-axis from bottom to top scanning, the same will be the x coordinate discretization, calculate a difference can be derived from the answer
Code:

#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((),());
    sort((),());
    (unique((),()),());
    for(auto ets : event)
    {
        if(ets[1]==0)
        {
            int id=lower_bound((),(),ets[2])-()+1;
            modify(id);
        }
        else
        {
            int id=upper_bound((),(),ets[2])-();
            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),(0),(0);
    T=1;
    //cin>>T;
    while(T--)
     {
         solve();
     }
     return 0;
}

Rocky P1908, in reverse order.

Yes, inverse-order pairs can also be done with scanline thinking. Consider converting finding the number of inverse-order pairs to enumerating each position from back to front\(i\), and find the number of times in the interval\([i+1,n]\) in which the size is in the interval\([0,a_i]\) The number of points in the The data range in the title is\(10^9\), it is clear that the first discretization, we can consider traversing the array from back to front, each traversal to a number when the update tree array (line tree), after the statistics of the current total number of how many numbers less than the current enumeration of the number, because we are from the back to front traversal, so smaller than the current number of the number of values is the number of his inverse pairs can be used to single-point modification of tree arrays or line trees and interval queries.

Necklace of Rock Valley P1972 [SDOI2009] HH

Short question: given a sequence, ask multiple times for the interval\([l,r]\) How many different numbers are in it.

This type of problem can be realized by considering the derivation of properties, followed by the use of a scan line enumerating all right endpoints and a data structure maintaining the answer for each left endpoint, or we can convert the problem to a two-dimensional plane and turn it into a rectangular query for information.

In this problem, we set the sequence\(a_i\) Last seen at\(pre_i\)If\(a_i\) There have been no occurrences, then\(pre_i = 0\). According to the question, if a kind of number occurs several times in the interval, it will produce only one contribution. It is useful to consider that the position at which each number produces a contribution is the position of the first occurrence in the interval, at which point it can be found that the total contribution produced is the\(pre_x \le l - 1\) of the number of the antiderivative is easy to prove.

Now the problem is namely: given a sequence\(pre\)Multiple query intervals\([l,r]\) How many of the\(pre_i \le l - 1\)。

We can put\(pre_i\) Looked at as a point in a two-dimensional plane:\(i\) are the horizontal coordinates, and\(pre_i\) is the vertical coordinate, the problem is transformed into a two-dimensional number point problem: each time you ask for the lower left corner of the\((l,0)\)The top right corner is\((r,l - 1)\) There are several points in the rectangle of

Noting that this query is differentiable, we can differentiate the query into the lower-left corner as\((0,0)\)The top right corner is\((r,l - 1)\) of the rectangle minus the lower left corner of\((0,0)\)The top right corner is\((l - 1,l - 1)\) The rectangle of has several points so that it is convenient for us to use the scan line idea.

single-operation complexity\(O(\log n)\)Total\(n\) Sub-additive operations and\(2m\) Sub-query operations, total time complexity\(O((n + m) \log n)\)。

Code:

#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((),());
  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),(0),(0);
  T=1;
  //cin>>T;
  while(T--)
   {
       solve();
   }
   return 0;
}

example

  • ROKKU P8593 "KDOI-02" one bomb drop Application of inverse order pairs.

  • AcWing 4709. triads A weaker version of the above question, again with an application to inverse order pairs.

  • Lugu P8773 [Blue Bridge Cup 2022 Province A] Selection Number Heteroscedasticity HH's necklace magic modification.

  • Rock Valley P8844 [Transworld Cup #4 Preliminaries] Cass and the Fallen Leaves Problems on Trees to Sequential Problems then 2D Counting Points.

In a nutshell, the main idea behind two-dimensional number points is that the data structure maintains one dimension and then enumerates the other.

bibliography

  • /yangsongyi/p/

  • /riba2534/article/details/76851233

  • /winddreams/article/details/38495093

  • /2022/10/01/sao-miao-xian

<Previous Next>