###### tags: `MDCPP講義` # 講義-線段樹-經典題講解 **Author : 謝侑哲** --- # 矩形覆蓋面積 ---- 先來讀題 ---- [矩形覆蓋面積](https://tioj.ck.tp.edu.tw/problems/1224) ---- 簡單來說，就是給你一堆矩形 矩形之間可能會有重疊 要你算出重疊完的面積是多少 ---- 舉個栗子 ----  這三塊矩形重疊的面積是22 (藍色6/紅色11/黃色5) ---- 遇到這種題目，第一個想法會是甚麼? ---- 我的話...? ---- 那就硬幹吧 ---- 把整張圖所有被蓋過的地方標上記號 再全部掃一遍 ---- 不過，如果那麼暴力就好 我們就不需要演算法了對吧 ---- 來計算一下時間複雜度吧? ---- 可以放的矩形最大的面積是N*N 並且可以放置N個 再加上最後要再掃過整個N*N的平面 最終複雜度是 : O(N*N+1) ---- 這題的N大小為1e6 配上這個複雜度就相當於要跑快3個小時才能跑完 ~~如果是總召的破筆電可能要快8小時~~ ---- 所以這個方法顯然不可行 ---- 讓我們加一點演算法吧 ---- 既然從二維的方式一路掃過去不可行 那我們可以來試試看一維的? ----  試著吧一行的數據當作單一資料 這樣我們只要掃N行過去 這樣就直接少掉N倍的時間了!!! ---- 這種方法我們給他一個特別的名稱 ---- ### 掃描線法 ---- 掃描線法顧名思義就是用一條線掃過去 ---- 其中在我們掃的過程中 線上會存取不同的資料 ----  可以顯然看出線上會是不斷變化的區間 ---- 看到不斷變化的區間 是時候用我們剛學到的線段樹了 ---- 只要開一棵線段樹 並且判斷那條線上標記的是矩形的結束或是開始 再進行矩形區段的修改就行了 ---- 圖解就像這樣 ----  ---- 不過想想會發現好像沒那麼單純 ---- 問題 不知道區間有幾個非0的數 ex: 矩形1 : 0 1 1 0 0 矩形2 : 0 2 2 0 0 當兩個矩形疊在一起覆蓋應是2 我們查他的區間值卻會是4 ---- 不過根據線段樹的特性可以解決這問題 ---- 因為線段樹的特性是修改時一次修改整個區間 所以我們當初才有lazytag的作法 ---- 這裡我們就改成直接判斷這個區間有沒有被標上tag 有就代表這個區間是被補滿的 ---- 再看一次問題 問題 不知道區間有幾個非0的數 ex: 矩形1 : 0 1 1 0 0 矩形2 : 0 2 2 0 0 如果我們改記tag，只要判定tag是否=0就可以知道這個區間是否填滿 這裡計算的話會發現，那塊重疊的區間tag會是2，長度是2 出來的值會是2 也就是說判定是否為0的方式會解決掉重疊問題 ---- code(不是我寫的): ```cpp= #include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=1000000+10 ; struct P { int x,d,u,val ; bool operator < (const P &rhs) const { return x<rhs.x ; } }a[200000+10]; int ST[5*maxn],tag[5*maxn] ; void modify(int l,int r,int L,int R,int id,int val) { if(l==L && r==R) { tag[id]+=val ; return ; } int mid=(L+R)/2 ; if(r<=mid) modify(l,r,L,mid,2*id,val) ; else if(l>mid) modify(l,r,mid+1,R,2*id+1,val) ; else modify(l,mid,L,mid,2*id,val) , modify(mid+1,r,mid+1,R,2*id+1,val) ; ST[id]= (tag[2*id] ? mid-L+1 : ST[2*id]) + (tag[2*id+1] ? R-mid : ST[2*id+1]) ; } main() { int n ; scanf("%d",&n) ; for(int i=0;i<n;i++) { int x1,y1,x2,y2 ; scanf("%d%d%d%d",&x1,&x2,&y1,&y2) ; a[2*i]=(P){x1,y1,y2-1,1} ; a[2*i+1]=(P){x2,y1,y2-1,-1} ; } sort(a,a+2*n) ; int x=0 , val=0 ; LL ans=0LL ; for(int i=0;i<2*n;i++) { ans+= (LL) (a[i].x-x)*val ; modify(a[i].d,a[i].u,0,maxn-1,1,a[i].val) ; x=a[i].x ; val=ST[1] ; } printf("%lld\n",ans) ; } ``` --- 關於一些錯誤的想法 ---- 這是我當初在想這題時 想的幾個方法 不過後來都發現他是錯誤的 但可能有人會有一樣的想法 所以就講一下 ---- 因為線段樹的特性是會把整個區域填滿 所以當填到重疊的地方時，總值會超過它的長度 ex : 0 1 0 0 \+ $\ .$ 1 1 1 1 總值為5，超過4 可不可以在update判斷 當子節點的值超過它的長度時 只上更新它的長度值 以上例就是往上傳4，也就是實際被填滿的格數 ---- 不過他有個問題是 當我們在進行矩陣的刪去時會出現以下的狀況 ----  先在[3,3]放上一個矩形 ----  再在[3,4]再放上一個一個矩形 ----  這時候[3,4]的那個矩形到末端，刪除 會發現原本留下的那個矩形會被忽略掉 ---- 所以這個方法不可行 ---- 第二個錯誤的vector紀錄 ---- 就是開一個vector的陣列 ```cpp= vector<int> arr[MAXN]; ``` 每有一個矩陣插進來就放入一個標記進入vector 如果子節點不是empty就上傳1 ---- 這個方法跟上面那個錯誤的方法很像 就是同樣面對刪掉大範圍的矩陣會爆掉 ---