IOI 1998 Picture ( Scanning Line, Segment Tree )

PEG Judge - IOI '98 - Picture

題意：
給很多矩形的左下角和右上角座標，問總周長為何。被包含的線段不算在周長裡。

資料規模：
The first line of the input contains the number of rectangles (0 ≤ number of rectangles < 5000) pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate. All coordinates are in the inclusive range [−10000, 10000] and any existing rectangle has a positive area.

解法：
掃描線，考慮對 X, Y 方向各做一遍。
考慮從下方掃描至上，將矩形離散為下方的邊為加入的事件，上方的邊為刪除的事件。只要不斷地加上和前一次事件掃描時的覆蓋長度差，就會得解。一個需要注意的地方是，線段重疊時的處理。如果刪除的事件發生在加入的事件以前，那麼會有重複算的情形，但是只要排序事件使得可以保證重疊時先處理加入的事件，就不會產生這方面的問題。至於線段樹本身細節的實作，考慮到實際上需要的是根節點儲存的「總覆蓋長度」這個資訊，那麼只要所有子節點紀錄這個資訊就能透過一般的 pull() 維護。接著考慮覆蓋操作的細節，當可覆蓋時直接改變「被完全覆蓋的次數」這個資訊，而這個次數若大於 1，「總覆蓋長度」自然是該節點的長度，否則用子節點的「總覆蓋長度」更新。另外這裡為了方便，用離散化線段樹處理。

另一種做法，是只做一次掃描線，所以額外維護當前有多少線段，線段數量的兩倍便是當前高度和前一次高度之間存在的邊數，只要將這些邊數乘上對應的高度差，就能同時完成縱邊的計算。至於維護線段數量，還需要額外維護節點的左界是否被覆蓋，和右界是否被覆蓋。當前這個節點若是被覆蓋的，那麼線段數量為 1，否則是左節點的線段數量 + 右節點的線段數量，但若左節點的右界被覆蓋，且右節點的左界被覆蓋，那麼還須再減 1。代碼在最下面。

時間 / 空間複雜度：
O( N lg N )

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

const int MAXN = 5000;

int N;
int L[ MAXN ], D[ MAXN ], R[ MAXN ], U[ MAXN ];

struct segt{
  int lb, rb;
  int cov;
  int cov_len;
  segt *lc, *rc;
  segt(){}
  segt( int ll, int rr ){
    lb = ll, rb = rr;
    cov = cov_len = 0;
    lc = rc = NULL;
  }
  void pull(){
    if( cov ){
      cov_len = rb - lb;
      return;
    }
    cov_len = ( lc ? lc->cov_len : 0 ) + ( rc ? rc->cov_len : 0 );
  }
} *root;

void update( segt *t, int ql, int qr, int v ){
  if( qr <= t->lb or t->rb <= ql ) return;
  if( ql <= t->lb and t->rb <= qr ){
    t->cov += v;
    t->pull();
    return;
  }
  int mid = t->lb + t->rb >> 1;
  if( not t->lc ){
    t->lc = new segt( t->lb, mid );
  }
  update( t->lc, ql, qr, v );
  if( not t->rc ){
    t->rc = new segt( mid, t->rb );
  }
  update( t->rc, ql, qr, v );
  t->pull();
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> L[ i ] >> D[ i ] >> R[ i ] >> U[ i ];
  }
  long long ans = 0;
  {
    root = new segt( *min_element( L, L + N ), *max_element( R, R + N ) );
    vector< tuple< int, int, int, int > > event;
    for( int i = 0; i < N; ++i ){
      event.emplace_back( D[ i ], 0, L[ i ], R[ i ] ); // 0 for in to prevent
      event.emplace_back( U[ i ], 1, L[ i ], R[ i ] ); // problems regarding overlap
    }
    sort( event.begin(), event.end() );
    for( int i = 0, prev_len = 0; i < 2 * N; ++i ){
      int y, t, ll, rr; tie( y, t, ll, rr ) = event[ i ];
      update( root, ll, rr, t ? -1 : 1 );
      ans += abs( root->cov_len - prev_len );
      prev_len = root->cov_len;
    }
  }
  {
    root = new segt( *min_element( D, D + N ), *max_element( U, U + N ) );
    vector< tuple< int, int, int, int > > event;
    for( int i = 0; i < N; ++i ){
      event.emplace_back( L[ i ], 0, D[ i ], U[ i ] ); // 0 for in to prevent
      event.emplace_back( R[ i ], 1, D[ i ], U[ i ] ); // problems regarding overlap
    }
    sort( event.begin(), event.end() );
    for( int i = 0, prev_len = 0; i < 2 * N; ++i ){
      int y, t, ll, rr; tie( y, t, ll, rr ) = event[ i ];
      update( root, ll, rr, t ? -1 : 1 );
      ans += abs( root->cov_len - prev_len );
      prev_len = root->cov_len;
    }
  }
  cout << ans << "\n";
  return 0;
}

.

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

const int MAXN = 5000;

int N;
int L[ MAXN ], D[ MAXN ], R[ MAXN ], U[ MAXN ];

struct segt{
  int lb, rb;
  int cov;
  int cov_len;
  bool cov_l, cov_r;
  int cov_cnt;
  segt *lc, *rc;
  segt(){}
  segt( int ll, int rr ){
    lb = ll, rb = rr;
    cov = cov_len = cov_l = cov_r = cov_cnt = 0;
    lc = rc = NULL;
  }
  void pull(){
    if( cov ){
      cov_len = rb - lb;
      cov_l = cov_r = cov_cnt = 1;
      return;
    }
    cov_len = ( lc ? lc->cov_len : 0 ) + ( rc ? rc->cov_len : 0 );
    cov_l = lc ? lc->cov_l : 0;
    cov_r = rc ? rc->cov_r : 0;
    cov_cnt = ( lc ? lc->cov_cnt : 0 ) + ( rc ? rc->cov_cnt : 0 ) - ( lc and rc and lc->cov_r and rc->cov_l );
  }
} *root;

void update( segt *t, int ql, int qr, int v ){
  if( qr <= t->lb or t->rb <= ql ) return;
  if( ql <= t->lb and t->rb <= qr ){
    t->cov += v;
    t->pull();
    return;
  }
  int mid = t->lb + t->rb >> 1;
  if( not t->lc ){
    t->lc = new segt( t->lb, mid );
  }
  update( t->lc, ql, qr, v );
  if( not t->rc ){
    t->rc = new segt( mid, t->rb );
  }
  update( t->rc, ql, qr, v );
  t->pull();
}

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> L[ i ] >> D[ i ] >> R[ i ] >> U[ i ];
  }
  long long ans = 0;
  {
    root = new segt( *min_element( L, L + N ), *max_element( R, R + N ) );
    vector< tuple< int, int, int, int > > event;
    for( int i = 0; i < N; ++i ){
      event.emplace_back( D[ i ], 0, L[ i ], R[ i ] ); // 0 for in to prevent
      event.emplace_back( U[ i ], 1, L[ i ], R[ i ] ); // problems regarding overlap
    }
    sort( event.begin(), event.end() );
    for( int i = 0, prev_len = 0, prev_hei = 0; i < 2 * N; ++i ){
      int y, t, ll, rr; tie( y, t, ll, rr ) = event[ i ];
      ans += 2LL * root->cov_cnt * ( y - prev_hei );
      update( root, ll, rr, t ? -1 : 1 );
      ans += abs( root->cov_len - prev_len );
      prev_len = root->cov_len;
      prev_hei = y;
    }
  }
  cout << ans << "\n";
  return 0;
}