掃描線是一種用來處理矩形相交的面積問題的算法?
漸近時間復雜度約為O(nlogn)O(nlogn)
Q1.
在坐標系給定n個矩形(以左下/右上角坐標給出)?
求這些矩形面積的并

例如下圖?
n=2?
矩形1: (1,1) (3,3)?
矩形2: (2,2) (4,4)?

A1.
掃描線的過程大致可以描述為?
將整個面積并 以n個矩形的 2n條縱邊為界 分割為2n-1個部分求解

即上圖中我們作如下分割求解?
?
我們要求的面積就是ans=S1+S2+S3ans=S1+S2+S3
再細致一點講?
我們記錄每條縱邊并按x坐標升序排序?
依次遍歷每條縱邊邊，同時記錄當前縱邊覆蓋的y軸總長度len?
遍歷到的縱邊為一個矩形的左邊界時，len增加?
反之為右邊界時，len減小?
根據當前遍歷到的縱邊ii更新完len后?
令ans+=(xi+1?xi)?lenans+=(xi+1?xi)?len （xi+1xi+1為下一條掃描線的橫坐標,xixi為當前掃描線橫坐標）

最關鍵的問題來了，len是如何更新的呢?
設一個矩形表示為(x1,y1)(x2,y2)(x1,y1)(x2,y2)?
我們記錄這個矩形的掃描線為兩個四元組?
(x1,y1,y2,k=1)(x2,y1,y2,k=?1)(x1,y1,y2,k=1)(x2,y1,y2,k=?1)其中左邊界記錄的掃描線k=1，右邊界則為-1?
最后我們共記錄了2n條掃描線

定義cov[i]=vcov[i]=v表示yy軸上ii共被覆蓋了vv次?
將這些掃描線按x升序排序后?
設當前遍歷到的掃描線為(xi,yi,1,yi,2,k)(xi,yi,1,yi,2,k)?
我們令cov[yi,1]cov[yi,1]~cov[yi,2]cov[yi,2]都加k，即更新此時的覆蓋情況?
那么此時有len=?1+∑cov[i]>01len=?1+∑cov[i]>01?
更新ans+=(xi+1?xi)?lenans+=(xi+1?xi)?len
對cov數組的更新顯然可以用線段樹優化?
且注意到這里掃描線的修改區間都是成對出現的(即一次+1一次-1)?
我們不采用延遲標記的方式?
而是直接修改每個區間對應的logn個結點

len[p]表示結點p表示的區間內被覆蓋的總長度?
對某個結點修改cov時和從下向上傳遞標記時?
進行如下更新

void pushup(int p,int ll,int rr) {if(cov[p]>0) len[p]=rr-ll;else if(ll==rr) len[p]=0;else len[p]=len[p<<1]+len[p<<1|1]; }

修改完后當前的總覆蓋區間就是len[rt]

注意掃描線的題一般y都很大，且存在浮點數
所以要對y進行離散化
(val[yi]val[yi]表示yiyi離散化后的數值，pos[i]pos[i]表示ii對應的原數值)?
離散化后對于四元組(xi,yi,1,yi,2,k)(xi,yi,1,yi,2,k)?
我們的更新區間為[val[yi,1],val[yi,2]?1][val[yi,1],val[yi,2]?1]
而對應的上推變為

void pushup(int p,int ll,int rr) {if(cov[p]>0) len[p]=pos[rr+1]-pos[ll];else if(ll==rr) len[p]=0;else len[p]=len[p<<1]+len[p<<1|1]; }

https://blog.csdn.net/weixin_43272781/article/details/83513482

https://blog.csdn.net/weixin_43272781/article/details/83514942

https://blog.csdn.net/weixin_43272781/article/details/83515346

總結

以上是生活随笔為你收集整理的扫描线的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。