---
# System prepended metadata

title: tioj 1224 矩形覆蓋面積計算

---

# tioj 1224 矩形覆蓋面積計算

https://tioj.ck.tp.edu.tw/problems/1224

* https://robert1003.github.io/2020/02/10/sweep-line-and-segment-tree.html
* 線段樹部份，用懶標來標示這個區間是否我0，如果懶標>0，帶標這個區間全部被加過一遍，也就沒有0，所以對應的線段樹節點值就是r-l。（懶標不要下推）
* 各節點區間的mid要重疊，否則mid到mid+1的長度會算不到

```cpp=
#include <bits/stdc++.h>
#define EB emplace_back
#define vci vector<int>
#define PII pair<int,int>
#define F first
#define S second
#define rep(X, a,b) for(int X=a;X<b;++X)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) (int)(a).size()
#define NL "\n"
#define LL long long

using namespace std;

const int N=1e6+10;
int tree[4*N]={0}, tag[4*N]={0};

void pull(int v, int l, int r){
    if(tag[v]) tree[v]=r-l;
    else if(r!=l) tree[v]=tree[2*v]+tree[2*v+1];
}

void modify(int v, int l, int r, int ul, int ur, int x){
    if(l==ul && r==ur){
        tag[v]+=x;
    }
    else{
        int mid=(l+r)>>1;
        if(ur<=mid) modify(2*v, l, mid, ul, ur, x);
        else if(ul>=mid) modify(2*v+1, mid, r, ul, ur, x);
        else{
            modify(2*v, l, mid, ul, mid, x);
            modify(2*v+1, mid, r, mid, ur, x);
        }
    }
    pull(v, l, r);
}

struct rec{
    int l, r, y, v;

    bool operator<(const rec& cmp) const{
        return y<cmp.y;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, l, r, d, u;
    cin>>n;
    vector<rec> gh;
    rep(i,0,n){
        cin>>l>>r>>d>>u;
        gh.push_back({l,r,d,1});
        gh.push_back({l,r,u,-1});
    }
    sort(ALL(gh)); // sort by button position

    LL ans=0, prevy=0;
    for(auto tmp:gh){
        if(tmp.y!=prevy){
            ans+=tree[1]*(tmp.y-prevy); // tree[1] is the sum of non-zero in the line
            prevy=tmp.y;
        }
        modify(1, 0, 1000000, tmp.l, tmp.r, tmp.v);
    }
    cout<<ans<<NL;
}
```