# 【TIOJ】 1224. Rectangular Coverage Area

## [題目連結](https://tioj.ck.tp.edu.tw/problems/1224)

## **時間複雜度**

* $O(NlogN)$

## **解題想法**

直接扣掉重疊面積好像有點難，又不太容易套二維資料結構，不如把每次覆蓋區域不一樣的地方都切成一條長條型，這樣要計算的東西就是 **覆蓋量 $\times$ 高度**，不過要怎麼維護覆蓋量？

當加入一個矩形的時候，必須要對區間都加一次值（代表多被覆蓋一次），同樣，當一個矩形被掃完的時候，必須要對區間都扣一次值（代表少被覆蓋一次），但是每次我想知道的是有多少非 $0$ 的值（代表覆蓋到的實際面積），

這樣就把原本的問題換成了區間操作的問題。

實作上可以使用線段樹，
由於在線段樹上一個區間可以被拆成 $logN$ 個區間，
所以在每個區間的值就是：

* 如果被蓋到，就是整個區間的長度
* 否則，回傳兩個子區間相加

這樣，總複雜度 $O(NlogN)$

## **完整程式**

值得注意的是這邊用 #define int long long 會掛掉，所以要單獨對答案維護 long long 型態

/* Question : TIOJ 1224. Rectangular Coverage Area */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define priq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second

#define nL cnt * 2
#define nR cnt * 2 + 1

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e6 + 50;
const int Mod = 1e9 + 7;
int n, l, r, d, u, res, seg[MAXN*4], lazy[MAXN*4];
vector<tuple<int, int, int, int>> side;

void dealt( int cnt, int L, int R ){
    if( lazy[cnt] ) seg[cnt] = R - L + 1;
    else if( L != R ) seg[cnt] = seg[nL] + seg[nR];
    else seg[cnt] = 0;
}

void update( int L, int R, int ul, int ur, int dt, int cnt ){
    if( ul <= L && R <= ur ){
        lazy[cnt] += dt;
        dealt(cnt, L, R);
        return;
    }

    int M = ( L + R ) / 2;

    if (ul <= M) update(L, M, ul, ur, dt, nL);
    if (M < ur) update(M+1, R, ul, ur, dt, nR);

    dealt(cnt, L, R);
}

signed main(){
    opt;
    cin >> n;
    for( int i = 0 ; i < n ; i++ ){
        cin >> l >> r >> d >> u;
        side.pb({l, d+1, u, 1});
        side.pb({r, d+1, u, -1});
    }

    sort(side.begin(), side.end());
    
    int pre = 0;
    long long ans = 0;
    
    for( auto [pos, d, u, dif] : side ){
        if( pos != pre ){
            ans += 1LL * ( pos - pre ) * seg[1];
            pre = pos;
        }
        
        update(1, 1000000, d, u, dif, 1);
    }

    cout << ans << "\n";
}