CFR 337 D. Vika and Segments ( = 矩形面積 Segment Tree + Scanning Line )

Problem - D - Codeforces
事實上應該有更好的解法，就是先把所有矩形的面積取和，再用BIT之類的結構維護一些東西，計算所有重疊的部分然後減去。但顯然也能直接當作是矩形面積覆蓋問題。因為後者比較有實用性，而且自己不太熟悉，我試著實現了後者。這是一個利用掃描線思想的經典算法，首先將所有矩形轉換成兩個線段，其左邊的縱直線，和右邊的縱直線，依 x座標由小到大觀察，每遇到一個矩形的左邊就當作是在垂直方向增加事件，遇到右邊就當作是在垂直方向消失的事件( 顯然會成對出現 )，每跳躍一段*水平距離，就將線段樹上管理的事件中還存在的節點數數量( 事件相互重疊後在垂直方向的總節點數 ) 乘上跳躍的水平距離，加於答案中。因此線段樹需要支持的操作有兩種，覆蓋一個區間，查詢整個線段一共有幾個點被覆蓋。想一下，就會發現這挺困難的( 至少我覺得很困難 )，需要一點靈感想到要維護這兩樣東西，線段樹上當前這個節點被完全覆蓋幾次，和假設這個節點沒有被完全覆蓋，它管理的區間有多少點被覆蓋( 遞迴詢問子節點 )。這麼一來，就能 O( lg N ) 完成操作和詢問了。
註：水平距離：對於任意兩個 x座標對應的所有事件都沒有增加或減少的那一段水平距離。
細節上需要注意的是，首先顯然要離散化，然後對於相同的 x座標，我是以左開右閉 [ l , r ) 的方式處理。這類統計面積或長度的問題離散化時，線段樹用左開右閉的方式處理會比較直觀。以這個題目的例子，若採取 [ l, r ] 的方式且使用一般的單點修改，假設我們想修改一段區間 [ 3, 10 ]，離散化後成為 [ 2, 3 ]，然後恰好2和3被分別完全覆蓋，且它們的父節點沒有被完全覆蓋的這種情況。總之我[ l, r ]的實現方法總是搞不定這些有的沒的，如果有人能幫我抓個 bug就很感謝啦，就貼再最底下讓它沉睡好了。
另外可以參考這篇：
code備忘錄: HOJ::Problem : 12 - 矩形面積覆蓋

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXABSXY = 1e9 + 9;
typedef long long ll;

int n;
#define y1 ____y1
#define x1 ____x1
int x1[ MAXN ], y1[ MAXN ], x2[ MAXN ], y2[ MAXN ];

struct ID{
    vector< int > val;
    map< int, int > id;
    void discretize( const vector< int > &vec ){
        val = vec;
        sort( val.begin(), val.end() );
        val.resize( unique( val.begin(), val.end() ) - val.begin() );
        for( int i = 0; i < val.size(); ++i )
            id[ val[ i ] ] = i;
    }
} mp;

struct Line{
    int x, y1, y2, v;
    Line( int _x = -1, int _y1 = -1, int _y2 = -1, int _v = -1 ):
        x( _x ), y1( _y1 ), y2( _y2 ), v( _v ){}
    bool operator < ( const Line &oth ) const{
        return x < oth.x;
    }
} line[ MAXN << 1 ];

struct itvt{
    int cover_cnt, uncover_val;
    int lb, rb;
    itvt *lc, *rc;
    itvt( int _l = -1, int _r = -1 ) : lb( _l ), rb( _r ), lc(NULL), rc(NULL){
        cover_cnt = uncover_val = 0;
    }
    void pull(){
        uncover_val = 0;
        if( lc->cover_cnt > 0 ) uncover_val += mp.val[ lc->rb ] - mp.val[ lc->lb ];
        else uncover_val += lc->uncover_val;
        if( rc->cover_cnt > 0 ) uncover_val += mp.val[ rc->rb ] - mp.val[ rc->lb ];
        else uncover_val += rc->uncover_val;
    }
    void update( int ql, int qr, int v ){
        if( qr <= lb || rb <= ql ) return;
        if( ql <= lb && rb <= qr ) return (void)( cover_cnt += v );
        lc->update( ql, qr, v );
        rc->update( ql, qr, v );
        pull();
    }
    int qsum(){
        return cover_cnt > 0 ? mp.val[ rb ] - mp.val[ lb ] : uncover_val;
    }
} *root;

itvt* buildItvt( int lb, int rb ){ // [ lb, rb )
    itvt *t = new itvt( lb, rb );
    if( lb + 1 == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid, rb );
    return t;
}

void solve(){
    vector< int > _vec;
    for( int i = 0; i < n; ++i )
        _vec.push_back( x1[ i ] ),
        _vec.push_back( y1[ i ] ),
        _vec.push_back( x2[ i ] + 1 ), // [ x1, x2 )
        _vec.push_back( y2[ i ] + 1 ); // [ y1, y2 )
    mp.discretize( _vec );
    for( int i = 0; i < n; ++i )
        line[ i ] = Line( mp.id[ x1[ i ] ], mp.id[ y1[ i ] ], mp.id[ y2[ i ] + 1 ], 1 ),
        line[ n + i ] = Line( mp.id[ x2[ i ] + 1 ], mp.id[ y1[ i ] ], mp.id[ y2[ i ] + 1 ], -1 );
    sort( line, line + n * 2 );
    ll ans = 0;
    root = buildItvt( 0, mp.val.size() );
    for( int i = 0; i < 2 * n; ++i ){
        int prex = ( i - 1 < 0 ? mp.val[ line[ i ].x ] : mp.val[ line[ i - 1 ].x ] );
        ans += (ll)( mp.val[ line[ i ].x ] - prex ) * root->qsum();
        root->update( line[ i ].y1, line[ i ].y2, line[ i ].v );
    }
    cout << ans << "\n";
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n; ++i ){
        scanf("%d%d%d%d", x1 + i, y1 + i, x2 + i, y2 + i);
        if( x1[ i ] > x2[ i ] ) swap( x1[ i ], x2[ i ] );
        if( y1[ i ] > y2[ i ] ) swap( y1[ i ], y2[ i ] );
    }
    solve();
    return 0;
}

// WA, [ l, r ]
/*
Input : 
2
1 1 20 20
11 11 20 20
Output :
240
Answer : 
400
// In the process it will have root->qsum() == 12 for some reason
*/
 #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXABSXY = 1e9 + 9;
typedef long long ll;

int n;
#define y1 ____y1
#define x1 ____x1
int x1[ MAXN ], y1[ MAXN ], x2[ MAXN ], y2[ MAXN ];

struct ID{
    vector< int > val;
    map< int, int > id;
    void discretize( const vector< int > &vec ){
        val = vec;
        sort( val.begin(), val.end() );
        val.resize( unique( val.begin(), val.end() ) - val.begin() );
        for( int i = 0; i < val.size(); ++i )
            id[ val[ i ] ] = i;
    }
} mp;

struct Line{
    int x, y1, y2, v;
    Line( int _x = -1, int _y1 = -1, int _y2 = -1, int _v = -1 ):
        x( _x ), y1( _y1 ), y2( _y2 ), v( _v ){}
    bool operator < ( const Line &oth ) const{
        return x < oth.x;
    }
} line[ MAXN << 1 ];

struct itvt{
    int cover_cnt, uncover_val;
    int lb, rb;
    itvt *lc, *rc;
    itvt( int _l = -1, int _r = -1 ) : lb( _l ), rb( _r ), lc(NULL), rc(NULL){
        cover_cnt = uncover_val = 0;
    }
    void pull(){
        if( lc->cover_cnt > 0 && rc->cover_cnt > 0 ) return (void)( uncover_val = mp.val[ rb ] - mp.val[ lb ] + 1 );
        uncover_val = 0;
        if( lc->cover_cnt > 0 ) uncover_val += mp.val[ lc->rb ] - mp.val[ lc->lb ] + 1;
        else uncover_val += lc->uncover_val;
        if( rc->cover_cnt > 0 ) uncover_val += mp.val[ rc->rb ] - mp.val[ rc->lb ] + 1;
        else uncover_val += rc->uncover_val;
    }
    void update( int ql, int qr, int v ){
        if( qr < lb || rb < ql ) return;
        if( ql <= lb && rb <= qr ) return (void)( cover_cnt += v );
        lc->update( ql, qr, v );
        rc->update( ql, qr, v );
        pull();
    }
    int qsum(){
        return cover_cnt > 0 ? mp.val[ rb ] - mp.val[ lb ] + 1 : uncover_val;
    }
} *root;

itvt* buildItvt( int lb, int rb ){
    itvt *t = new itvt( lb, rb );
    if( lb == rb ) return t;
    int mid = lb + rb >> 1;
    t->lc = buildItvt( lb, mid );
    t->rc = buildItvt( mid + 1, rb );
    return t;
}

void solve(){
    vector< int > _vec;
    for( int i = 0; i < n; ++i )
        _vec.push_back( x1[ i ] ),
        _vec.push_back( y1[ i ] ),
        _vec.push_back( x2[ i ] + 1 ), // [ x1, x2 )
        _vec.push_back( y2[ i ] );
    mp.discretize( _vec );
    for( int i = 0; i < n; ++i )
        line[ i ] = Line( mp.id[ x1[ i ] ], mp.id[ y1[ i ] ], mp.id[ y2[ i ] ], 1 ),
        line[ n + i ] = Line( mp.id[ x2[ i ] + 1 ], mp.id[ y1[ i ] ], mp.id[ y2[ i ] ], -1 );
    sort( line, line + n * 2 );
    ll ans = 0;
    root = buildItvt( 0, mp.val.size() - 1 );
    for( int i = 0; i < 2 * n; ++i ){
        int prex = ( i - 1 < 0 ? mp.val[ line[ i ].x ] : mp.val[ line[ i - 1 ].x ] );
        ans += (ll)( mp.val[ line[ i ].x ] - prex ) * root->qsum();
        root->update( line[ i ].y1, line[ i ].y2, line[ i ].v );
    }
    cout << ans << "\n";
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n; ++i ){
        scanf("%d%d%d%d", x1 + i, y1 + i, x2 + i, y2 + i);
        if( x1[ i ] > x2[ i ] ) swap( x1[ i ], x2[ i ] );
        if( y1[ i ] > y2[ i ] ) swap( y1[ i ], y2[ i ] );
    }
    solve();
    return 0;
}