掃描線學習筆記
今天初學了掃描線，發一篇學習筆記鞏固一下
掃描線能干什么
- 計算矩形面積的并
- 計算矩形周長的并
- 其他
引入
如下圖所示，給定平面直角坐標系內N個矩形，求矩形的面積并，定義面積的并為矩形并集覆蓋坐標系的面積和
正文部分
面積并：
通過觀察，我們發現，對于矩形面積的并，可以通過以每個矩形左右邊為分界，分成若干小的規則矩形，所以，我們引入了一種新的思想——掃描線。
顧名思義，這種思想在坐標系內構想了一條從左到右掃描整個坐標系的直線，它在每個矩形的邊停頓并更新答案，如下圖，紅線即為掃描線，這種思想即為掃描線法。
那么我們思考最終答案，根據引入所言，不難注意到，我們在通過掃描線把面積并分成了若干規則圖形，通過矩形計算公式即可輕易計算出每部分的答案，具體而言，我們記錄每一個掃描線停頓位置的橫坐標，定為\(x_1 , x_2 ,x_3 ,x_n\) 對于每一個位置矩形的面積我們可以得出\(S=(x_i-x_{i-1})\times h\)(\(h\)為掃描線此時高度),最后，各掃描線停頓位置之和即為所求。
我們如何維護答案呢，對于每一個停頓位置，我們可以有四元組\((x,y1,y2,d)\)，其中，x為橫坐標，\(y1,y2\)為在\(x_i\)處掃描線與整個圖形的最低交點和最高交點,對于左邊界，\(d=1\)，對于右邊界\(d=-1\),如圖
同時，我們給每一個經過縱坐標排序，維護\(raw\)數組，對于\(raw[i]\)，表示從\(y_i\)的坐標，掃描線被每條上下邊界分成若干段，對于一段\([y_{i-1},y_i]\)，可以用\(raw\)數組表示。
我們再維護一個數組\(c\)，\(c[i]\)表示到目前位置，第\(i\)個位置被覆蓋的次數，按\(x\)升序遍歷四元組，每次給\([y_1,y_2]\)每一段加上\(d\)，\(c[i]>0\)表示這個區間目前仍被覆蓋，\(\sum_{c[i]>0}{raw[i]-raw[i-1]}\)即為掃描線到當前節點的\(h\)，統計答案即可，至此我們得到了\(O(n^2)\)做法。
觀察上述求解過程，我們在對\(c\)數組做區間修改并訪問整個\(raw\)數組區間和，不難想到，我們可以用線段樹維護。不同與普通線段樹，我們只需要訪問樹根的值，所以，我們可以省略push_down操作，改為維護兩個數組\(len\)和\(cnt\)，\(cnt[i]\)表示對于當前線段樹節點的\([l,r]\)被覆蓋了幾次\(len[i]\)表示，當前節點\([l,r]\)對于\(h\)的貢獻。顯然，整體的\(h\)就是根節點的\(len\)，值得注意的是，push_up操作有所不同，如果當前節點的\(cnt>0\),表示當前節點對應的\([l,r]\)，被全覆蓋，所以再加上子節點的貢獻就重復了，此時\(len[i]=raw[r+1]-raw[l]\)，否則，就通過子節點更新。同時，因為更新\(len\)值可能是通過子節點，所以，在該節點被全部包含也就是\(return\)之前，也要push_up。
最后提醒一句，大部分掃描線需要離散化。
線段樹部分:
#define lx x<<1
#define rx (x<<1)+1
void build(int tl,int tr,int x)
{
l[x]=tl,r[x]=tr;
if(l[x]==r[x]) return;
int mid=(l[x]+r[x])>>1;
build(tl,mid,lx);
build(mid+1,tr,rx);
}
void push_up(int x)
{
if(cnt[x]>0) len[x]=raw[r[x]+1]-raw[l[x]];
else len[x]=len[lx]+len[rx];
}
void modify(int dl,int dr,int x,int d)
{
if(dl<=l[x] && dr>=r[x])
{
cnt[x]+=d;
push_up(x);
return;
}
int mid=(l[x]+r[x])>>1;
if(dl<=mid) modify(dl,dr,lx,d);
if(dr>mid) modify(dl,dr,rx,d);
push_up(x);
}
周長的并：
定義類比面積并。
我們在維護面積并時用到了掃描線停頓位置的\(h\)，顯然，這對于求周長并是很有幫助的。
先給出結論：
將四元組按照\(x\)為第一關鍵字，\(d\)為第二關鍵字排序后，有：
\(C=\vert \sum_{i=1}^{n}{h_i-h_{i-1}} \rvert+\vert\sum_{i=1}^{n}{w_i-w_{i-1}}\rvert\)（其中\(h\)為橫向掃描的高度，\(w\)為縱向掃描的寬度）
隨便畫幾個矩形，手模一下就可以發現\(\vert h_i-h_{i-1}\rvert\)實際上就是兩增加的長度，每次加上$ \Delta h$最終一定是周長左右長度，跑兩邊就是整個周長。那為什么還要按照 \(d\) 排序呢？觀察發現，如果前一個矩形和后一個矩形的左邊和右邊重合，實際上前一個矩形的右邊是沒有全部作為周長的，但是由于$ d=1$ 所以，你的代碼會將它誤認為沒有邊覆蓋它了，也就是全部作為周長的一部分了。這就需要將這個位置所有覆蓋的邊全部先加上，然后再去判斷是否覆蓋（感性理解一下，不懂的可以用desmos畫圖手玩一下），其他的正常跑兩邊線段樹即可。
模板：P1856 [IOI 1998 / USACO5.5] 矩形周長 Picture
代碼：
#include<bits/stdc++.h>
#define lx x<<1
#define rx (x<<1)+1
#define x1 qqq
#define x2 www
#define y1 eee
#define y2 rrr
using namespace std;
const int N=5e4;
int X[N],Y[N];
struct A
{
int x1,x2;
int y1,y2;
}sq[2*N];
struct B
{
int x;
int yl,yh;
int vl;
} line[2*N];
struct C
{
int y;
int xf,xb;
int vl;
} level[N];
int len[8*N],cnt[8*N],l[8*N],r[8*N];
int mx,my,pos;
int n;
void dis()
{
sort(X+1,X+2*n+1);
mx=unique(X+1,X+2*n+1)-(X+1);
sort(Y+1,Y+2*n+1);
my=unique(Y+1,Y+2*n+1)-(Y+1);
}
int askx(int x)
{
return lower_bound(X+1,X+mx+1,x)-X;
}
int asky(int x)
{
return lower_bound(Y+1,Y+my+1,x)-Y;
}
void build(int tl,int tr,int x)
{
l[x]=tl,r[x]=tr,len[x]=cnt[x]=0;
if(tl==tr) return;
int mid=(l[x]+r[x])>>1;
build(l[x],mid,lx);
build(mid+1,r[x],rx);
}
void push_up(int x,int k)
{
if(k==1)
{
if(cnt[x]) len[x]=X[r[x]+1]-X[l[x]];
else len[x]=len[lx]+len[rx];
}
if(k==2)
{
if(cnt[x]) len[x]=Y[r[x]+1]-Y[l[x]];
else len[x]=len[lx]+len[rx];
}
}
void modify(int dl,int dr,int x,int d,int k)
{
if(dl<=l[x] && dr>=r[x])
{
cnt[x]+=d;
push_up(x,k);
return;
}
int mid=(l[x]+r[x])>>1;
if(dl<=mid)modify(dl,dr,lx,d,k);
if(dr>mid) modify(dl,dr,rx,d,k);
push_up(x,k);
}
bool cmp(B a,B b)
{
if(a.x==b.x) return a.vl>b.vl;
return a.x<b.x;
}
bool cnp(C a,C b)
{
if(a.y==b.y) return a.vl>b.vl;
return a.y<b.y;
}
int main(){
// freopen("text.in","r",stdin);
// freopen("text.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
sq[i]=(A){x1,x2,y1,y2};
X[i]=x1;
X[i+n]=x2;
Y[i]=y1;
Y[i+n]=y2;
}
dis();
for(int i=1;i<=n;i++)
{
int x1=sq[i].x1,x2=sq[i].x2,y1=sq[i].y1,y2=sq[i].y2;
line[++pos]=(B){askx(x1),asky(y1),asky(y2),1};
level[pos]=(C){asky(y1),askx(x1),askx(x2),1};
line[++pos]=(B){askx(x2),asky(y1),asky(y2),-1};
level[pos]=(C){asky(y2),askx(x1),askx(x2),-1};
}
build(1,pos-1,1);
int ans=0,last=0;
sort(line+1,line+pos+1,cmp);
for(int i=1;i<=pos;i++)
{
modify(line[i].yl,line[i].yh-1,1,line[i].vl,2);
int now=len[1];
// cout<<i<<" "<<len[1]<<endl;
ans+=abs(now-last);
last=now;
}
build(1,pos-1,1);
last=0;
sort(level+1,level+pos+1,cnp);
for(int i=1;i<=pos;i++)
{
modify(level[i].xf,level[i].xb-1,1,level[i].vl,1);
int now=len[1];
ans+=abs(now-last);
last=now;
}
cout<<ans;
}
其他：
正如上文所言，掃描線是一種思想，我們可以把一些其他要維護的東西替換掉\(h\)，運用同樣的思路推廣出不同的解法
例題：P1502 窗口的星星
稍微點撥一下：
可以把星星的亮度和作為維護對象，把每個可以至少覆蓋到這顆星星的位置看做一個矩形。
正解及代碼請參考題解。
結語：
到這里，掃描線的入門部分就結束啦，作為一種思想，我們還需要把它運用到題目中才可以熟練掌握，另外的，掃描線還可以運用到其他坐標系問題中，比如二維數點，B維正交范圍，當然，本文為掃描線入門，更高深的內容請移步dalao們的博客，等作者學習之后也會更，也許吧。
完結撒花~
都讀到這里了，如果您覺得本文不錯可以給個贊嗎， rp++。
浙公網安備 33010602011771號