# 矩形覆蓋面積計算(線段樹應用)

* 先對所有座標對y由小到大排序(對y掃描)，一個Rectangle記得要拆y上下標，下標1標示進入到此Rectangle，並取此區間大小(mid-left or right-mid)，-1表示離開此Rectangle，並對線段樹此區間表示為0，表示改取此node value，不能整個取間都取
* 此時點的數目已經到2倍的y，對2*y做for loop，每一次需紀錄這次的y和segment[1]的值，在這一次y值和上一次y值相減並上segment[1]，segment[1]表示目前的矩形寬度
* 因為是線段緣故，做分治法時候，Mid記得兩段要重疊
* 使用tag來表示此線段是有被cover以及次數
* 如下圖，當一開始把需要把A.x=1和B.x=6插入到線段樹，
* 當一開始把需要把A.x=1和B.x=6插入到線段樹，建立一個線段樹如下，區間為1-7，tag和num均為0
* 使用分治法，分別往下尋找對應節點modify，終止條件為下面a和b
a. 為詢問區間在線段樹區間左(qr<left)或右(ql>right)，return
b. 詢問區間已經cover線段樹區間，且依照此時y是上標還下標，如果是下標，tag標記+1，表示此時需要利用此段作面積計算，-1表示離開此區間，此段已經離開，return
- !!!條件b成立後，不用設定num值，因為其母節點會依照子節點的tag判斷
- tag一方面也是記錄此interval的cover次數，當為0，表示此段已經沒有被整段cover，需要取該此節點的值(可理解為部分cover，例如1-5 tag為0但其值為2，表示其子節點3-5可能被cover且tag不為0但是1-2沒有)
- 當tag已經有被標記，其子節點有變化，母節點取值時候依然會取整段區間，且不用下推給leaf
- 當母節點取值時候，有tag>=1取該子節點整段(mid-l or r-mid)，tag==0取該節點的值，並且一路返回root
- 只要取root-segment[1]的num就知道現在x的區間有多大，可求得目前面積
- segment本身節點編號以及存的值，不必依照對應的資料陣列或是去存取區間，例如node 2一定要存data[2]或是存1-3資訊，透過2分查找方式，就可以知道其node段應的區間(重要的是查找區間)
* 可用GDB設定斷點除錯 
- 簡介 Debugger 按鈕作用，在上面範例中，我稍微講一下這些按鈕在做啥。
- 第一個按鈕：繼續（Continue），按下去後會持續跑，直到下個中斷點。
- 第二個按鈕：不進入函式（Step over），按下去後，會到在目前這 Function 跑到下一個敘述。
- 第三個按鈕：逐步執行（Step into），按下去後，會進入到每一部 Function 執行敘述並中斷。
- 第四個按鈕：逐步執行（Step out），按下去後，會直接把 Function 執行完並中斷。
- 第五個按鈕：重新起動，重跑 GDB 偵錯。
- 第六個按鈕：停止，停止 GDB 偵錯。
- Ref: https://blog.yangjerry.tw/vscode-cpp-2021-part2/

- 幾何題目可用ggb輔助畫圖幫忙
- https://www.geogebra.org/classic?lang=zh-TW
- 程式碼參考如下(但交大題目有x y為負數，建議x拆開為正座標和負座標兩段分開處理，再加總，y座標因為會大減小，負數無訪)

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define N 100005
#define M 1000001
#define lld long long
using namespace std;
int n;

struct Node{    //每一個矩陣分成上下兩條邊
    int x1;     //矩形左界x1
    int x2;     //矩形右界x2
    int y;      //矩形y座標（分上下兩邊）
    int val;    //val = ±1(進入代表1、離開代表-1)
    
}arr[2*N], arrN[2*N];

//seg[i]表示i的左右兩子樹的區間非0的個數
struct node{    //建立線段樹
    int val;    //維護非0個數
    int tag;    //使用tag紀錄區間被覆蓋次數
    
}seg[4*M], segN[M<<2]; // seg: Positive intervel, segN: Negative interval

bool cmp(Node a, Node b){
    return a.y<b.y;
}

//對區間[ql,qr)進行加值val
void modify(int cur,int l,int r,int ql,int qr,int val){
    if(r <= l || ql >= r || qr <= l)return;
    if(ql <= l && qr >= r){
        seg[cur].tag += val;
        return;
    }
    int mid = (l+r)/2;
    modify(2*cur,l,mid,ql,qr,val);
    modify(2*cur+1,mid,r,ql,qr,val);
    
    //左右節點如有tag表示被完全覆蓋，直接加上區間大小，否則加上seg[左右子樹]
    seg[cur].val = (seg[2*cur].tag?mid-l:seg[2*cur].val)
                  +(seg[2*cur+1].tag?r-mid:seg[2*cur+1].val);
}

int main(){
    ios;
    memset(arr,0,sizeof(arr));
    memset(seg,0,sizeof(seg));
    
    cin>>n;                                   //依序輸入左右下上：x1,y1,x2,y2
    for(int i=0;i<(n<<1);i+=2){
        int x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2); 
        if(x1<=0 && x2<=0){                   //x1, x2均<=0
            arr[i] = Node{0,0,y1,1};          //插入矩形下邊，帶入val = 1
            arr[i+1] = Node{0,0,y2,-1};       //上邊要val = -1
            arrN[i]=Node{abs(x2),abs(x1),y1,1};
            arrN[i+1]=Node{abs(x2),abs(x1),y2,-1};
        }
        else if(x1<=0 && x2>=0){                //x1<=0, x2>=0
            arr[i] = Node{0,x2,y1,1};          //插入矩形下邊，帶入val = 1
            arr[i+1] = Node{0,x2,y2,-1};       //上邊要val = -1
            arrN[i]=Node{0,abs(x1),y1,1};
            arrN[i+1]=Node{0,abs(x1),y2,-1};
        }
        else if(x1>=0 && x2>=0){                //x1, x2均>=0
            arr[i] = Node{x1,x2,y1,1};          //插入矩形下邊，帶入val = 1
            arr[i+1] = Node{x1,x2,y2,-1};       //上邊要val = -1
            arrN[i]=Node{0,0,y1,1};
            arrN[i+1]=Node{0,0,y2,-1};
        }
    }
    stable_sort(arr,arr+(n<<1),cmp);          //依照y座標由小到大排序
    stable_sort(arrN,arrN+(n<<1),cmp); 
    
    int y0 = 0,val = 0;                       //有下而上的枚舉所有水平邊
    lld ans = 0LL;                            //上一條y的座標，計算高，val為矩形結合起來的寬
    for(int i=0;i<(n<<1);i++){                //枚舉2n條y的邊
        ans += abs((lld)(arr[i].y-y0)*val);        //計算正區間面積（寬*高）
        ans += abs((lld)(arrN[i].y-y0n)*valn);    //計算負區間面積（寬*高）
        modify(seg,1,0,M,arr[i].x1,arr[i].x2,arr[i].val);  //對正線段樹加值
        modify(segN,1,0,M,arrN[i].x1,arrN[i].x2,arrN[i].val); //對負線段樹加值
        y0 = arr[i].y;  //紀錄此次正區間的y值
        y0n = arrN[i].y;  //紀錄此次負區間的y值
        val = seg[1].num; //修改後（下一輪）的正區間矩形寬度
        valn = segN[1].num; //修改後（下一輪）的負區間矩形寬度  
        cout<<ans<<'\n';
}

#### Ref: https://peienwu.com/seg2-5/

{%hackmd @alanlai/BJjLOLA6F %}