99久久久免费精品国产,国产精品成年片在线观看

C++掃描線思維

當(dāng)前位置：點(diǎn)晴教程→知識(shí)管理交流 →『技術(shù)文檔交流』

freeflydom

2024年12月2日 10:15 本文熱度 1763

引入

掃描線一般運(yùn)用在圖形上面，它和它的字面意思十分相似，就是一條線在整個(gè)圖上掃來掃去，它一般被用來解決圖形面積，周長(zhǎng)，以及二維數(shù)點(diǎn)等問題。

Atlantis 問題

題意

在二維坐標(biāo)系上，給出多個(gè)矩形的左下以及右上坐標(biāo)，求出所有矩形構(gòu)成的圖形的面積。

解法

根據(jù)圖片可知總面積可以直接暴力即可求出面積，如果數(shù)據(jù)大了怎么辦？這時(shí)就需要講到 掃描線 算法。

過程

現(xiàn)在假設(shè)我們有一根線，從下往上開始掃描：

如圖所示，我們可以把整個(gè)矩形分成如圖各個(gè)顏色不同的小矩形，那么這個(gè)小矩形的高就是我們掃過的距離，那么剩下了一個(gè)變量，那就是矩形的長(zhǎng)一直在變化。
我們的線段樹就是為了維護(hù)矩形的長(zhǎng)，我們給每一個(gè)矩形的上下邊進(jìn)行標(biāo)記，下面的邊標(biāo)記為 1，上面的邊標(biāo)記為 -1，每遇到一個(gè)矩形時(shí)，我們知道了標(biāo)記為 1 的邊，我們就加進(jìn)來這一條矩形的長(zhǎng)，等到掃描到 -1 時(shí)，證明這一條邊需要?jiǎng)h除，就刪去，利用 1 和 -1 可以輕松的到這種狀態(tài)。
還要注意這里的線段樹指的并不是線段的一個(gè)端點(diǎn)，而指的是一個(gè)區(qū)間，所以我們要計(jì)算的是 \(r+1\) 和 \(r-1\)。
需要離散化。

實(shí)現(xiàn)

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

練習(xí)

「POJ1151」Atlantis
「POJ1177」Picture
「POJ3832」Posters
洛谷 P1856[IOI1998][USACO5.5] 矩形周長(zhǎng) Picture

B 維正交范圍

B 維正交范圍指在一個(gè) B 維直角坐標(biāo)系下，第 \(i\) 維坐標(biāo)在一個(gè)整數(shù)范圍 \([l_i,r_i]\) 間，內(nèi)部的點(diǎn)集。

一般來說，一維正交范圍簡(jiǎn)稱區(qū)間，二維正交范圍簡(jiǎn)稱矩形，三維正交范圍簡(jiǎn)稱立方體（我們常說的二維數(shù)點(diǎn)就是二維正交范圍）。

對(duì)于一個(gè)靜態(tài)的二維問題，我們可以使用掃描線掃一維，數(shù)據(jù)結(jié)構(gòu)維護(hù)另一維。
在掃描線從左到右掃的過程中，會(huì)在數(shù)據(jù)結(jié)構(gòu)維護(hù)的那一維上產(chǎn)生一些修改與查詢。
如果查詢的信息可差分的話直接使用差分，否則需要使用分治。差分一般用樹狀數(shù)組和線段樹維護(hù)，但因?yàn)闃錉顢?shù)組好寫而且常數(shù)小，所以大部分人會(huì)選擇用樹狀數(shù)組來維護(hù)。分治一般是 CDQ 分治（但是這里不涉及分治）。

另一種比較容易理解的看待問題的角度是站在序列角度，而不站在二維平面角度。如果我們這樣看待問題，則掃描線實(shí)際上是枚舉了右端點(diǎn) \(r=1\cdots n\)，維護(hù)一個(gè)數(shù)據(jù)結(jié)構(gòu)，支持查詢對(duì)于當(dāng)前的 \(r\)，給定一個(gè)值 \(l\)，\(l\) 到 \(r\) 的答案是什么。即掃描線掃詢問右端點(diǎn)，數(shù)據(jù)結(jié)構(gòu)維護(hù)所有左端點(diǎn)的答案，或者說遍歷一維，數(shù)據(jù)結(jié)果維護(hù)另一維。

復(fù)雜度一般為 \(O((n+m)\log n)\)。

二維數(shù)點(diǎn)

給一個(gè)長(zhǎng)為 \(n\) 的序列，有 \(m\) 次查詢，每次查區(qū)間 \([l,r]\) 中值在 \([x,y]\) 內(nèi)的元素個(gè)數(shù)。

這個(gè)問題就叫做二維數(shù)點(diǎn)。我們可以發(fā)現(xiàn)等價(jià)于我們要查詢一個(gè)二維平面上矩形內(nèi)的點(diǎn)的數(shù)量和。這里講一下這個(gè)問題最簡(jiǎn)單的處理方法，掃描線 + 樹狀數(shù)組。

很顯然，這個(gè)問題是一個(gè)靜態(tài)的二維問題，我們通過掃描線可以將靜態(tài)的二維問題轉(zhuǎn)換為動(dòng)態(tài)的一維問題。維護(hù)動(dòng)態(tài)的一維問題就使用數(shù)據(jù)結(jié)構(gòu)維護(hù)序列，這里可以使用樹狀數(shù)組。

先將所有的詢問離散化，用樹狀數(shù)組維護(hù)權(quán)值，對(duì)于每次詢問的 \(l\) 和 \(r\)，我們?cè)诿杜e到 \(l-1\) 時(shí)統(tǒng)計(jì)當(dāng)前位于區(qū)間 \([x,y]\) 內(nèi)的數(shù)的數(shù)量 \(a\)，繼續(xù)向后枚舉，枚舉到 \(r\) 時(shí)統(tǒng)計(jì)當(dāng)前位于區(qū)間 \([x,y]\) 內(nèi)的數(shù)的數(shù)量 \(b\)，\(b-a\) 即為該次詢問的答案。

例題

洛谷 P2163[SHOI2007] 園丁的煩惱

題意：求\([x1,x2],[y1,y2]\)區(qū)間內(nèi)有多少個(gè)點(diǎn)
思路，可以用掃描線+樹狀數(shù)組來做，按y軸從下到上掃描，同是將x坐標(biāo)離散化，計(jì)算一個(gè)差分即可得出答案
代碼：

#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 逆序?qū)?/a>

沒錯(cuò)，逆序?qū)σ部梢杂脪呙杈€的思維來做。考慮將求逆序?qū)Φ膫€(gè)數(shù)轉(zhuǎn)化為從后向前枚舉每個(gè)位置 \(i\)，求在區(qū)間 \([i+1,n]\) 中，大小在區(qū)間 \([0,a_i]\) 中的點(diǎn)的個(gè)數(shù)。題目中數(shù)據(jù)范圍為 \(10^9\)，很顯然要先進(jìn)行離散化，我們可以考慮從后向前遍歷數(shù)組，每次遍歷到一個(gè)數(shù)時(shí)更新樹狀數(shù)組（線段樹），之后統(tǒng)計(jì)當(dāng)前一共有多少個(gè)數(shù)小于當(dāng)前枚舉的數(shù)，因?yàn)槲覀兪菑暮笙蚯氨闅v的，所以比當(dāng)前值小的數(shù)的個(gè)數(shù)就是他的逆序?qū)Φ膫€(gè)數(shù)，可以用樹狀數(shù)組或線段樹進(jìn)行單點(diǎn)修改和區(qū)間查詢。

洛谷 P1972 [SDOI2009] HH 的項(xiàng)鏈

簡(jiǎn)要題意：給定一個(gè)序列，多次詢問區(qū)間 \([l,r]\) 中有多少種不同的數(shù)。

這類問題我們可以考慮推導(dǎo)性質(zhì)，之后使用掃描線枚舉所有右端點(diǎn)，數(shù)據(jù)結(jié)構(gòu)維護(hù)每個(gè)左端點(diǎn)的答案的方法來實(shí)現(xiàn)，我們也可以將問題轉(zhuǎn)換到二維平面上，變?yōu)橐粋€(gè)矩形查詢信息的問題。

在本題中，我們?cè)O(shè)序列中 \(a_i\) 上一次出現(xiàn)的位置為 \(pre_i\)，如果 \(a_i\) 沒有出現(xiàn)過，則 \(pre_i = 0\)。根據(jù)題意，如果一種數(shù)在區(qū)間中出現(xiàn)多次，只會(huì)產(chǎn)生一次貢獻(xiàn)。不妨認(rèn)為每種數(shù)產(chǎn)生貢獻(xiàn)的位置是區(qū)間中第一次出現(xiàn)的位置，這時(shí)可以發(fā)現(xiàn)，產(chǎn)生的總貢獻(xiàn)即為 \(pre_x \le l - 1\) 的個(gè)數(shù)，反證法易證。

現(xiàn)在問題即為：給定一個(gè)序列 \(pre\)，多次查詢區(qū)間 \([l,r]\) 中有多少個(gè) \(pre_i \le l - 1\)。

我們可以把 \(pre_i\) 看成二維平面的點(diǎn)：\(i\) 是橫坐標(biāo)，\(pre_i\) 是縱坐標(biāo)，問題就轉(zhuǎn)化為了二維數(shù)點(diǎn)問題：每次詢問左下角為 \((l,0)\)，右上角為 \((r,l - 1)\) 的矩形中有幾個(gè)點(diǎn)。

注意到這個(gè)詢問是可差分的，我們可以將詢問差分為左下角為 \((0,0)\)，右上角為 \((r,l - 1)\) 的矩形減去左下角為 \((0,0)\)，右上角為 \((l - 1,l - 1)\) 的矩形有幾個(gè)點(diǎn)，這樣方便我們使用掃描線思想。

單次操作復(fù)雜度 \(O(\log n)\)，共有 \(n\) 次加點(diǎn)操作和 \(2m\) 次查詢操作，總時(shí)間復(fù)雜度 \(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;
}