CFR 609 F. Frogs and mosquitoes ( Discretization, Segment Tree, Binary Search )

Problem - 609F - Codeforces

題意：
有 N 隻青蛙在一維數線上，用位置和舌頭長度描述。現在依序有 M 隻蚊子出現，用位置和營養值描述。一個在位置 x，舌頭長度 t 的青蛙可以吃位於位置 y 的蚊子若且唯若 x ≤ y ≤ x + t，而且這隻青蛙是所有能吃到這隻蚊子的青蛙裡座標最小的。吃掉一個價值 v 的蚊子的青蛙的舌頭會立刻增長 v 單位長度。問最後每隻青蛙分別吃了幾隻蚊子，最後的舌頭長度是多少。

制約：
First line contains two integers n, m (1 ≤ n, m ≤ 2e5) — the number of frogs and mosquitoes.
Each of the next n lines contains two integers xi, ti (0 ≤ xi, ti ≤ 1e9) — the position and the initial length of the tongue of the i-th frog. It is guaranteed that all xi are different.
Next m lines contain two integers each pj, bj (0 ≤ pj, bj ≤ 1e9) — the position and the size of the j-th mosquito.

解法：
用動態開點的線段樹記錄區間上的青蛙舌頭可以伸到的最大座標。當一個蚊子進來的時候，在線段樹上進行二分搜，也就是在蚊子的座標以左的區間裡搜尋，若左半區間存在一個青蛙可以伸到蚊子的座標以右，就往左邊，否則往右邊。如果進來的這隻蚊子沒有青蛙吃得到，就把它存在一個二元搜尋樹的結構裡，等一隻青蛙吃到蚊子而舌頭變長的時候，再二分搜出該青蛙座標 lower_bound 的蚊子座標，一直吃直到吃不到。

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

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

const int MAXN = int( 2e5 );
const int MAXX = int( 1e9 );

int N, M;
int X[ MAXN ], T[ MAXN ];

struct segt {
  int lb, rb;
  long long maxreach;
  segt *lc, *rc;
  segt( int _l = 0, int _r = 0 ) {
    lb = _l, rb = _r;
    maxreach = 0;
    lc = rc = NULL;
  }
  void pull() {
    maxreach = max( lc ? lc->maxreach : 0LL, rc ? rc->maxreach : 0LL );
  }
  void modify( int k, long long v ) {
    if( lb + 1 == rb ) {
      maxreach = v;
      return;
    }
    int mid = lb + rb >> 1;
    if( k < mid ) {
      if( not lc ) {
        lc = new segt( lb, mid );
      }
      lc->modify( k, v );
    } else {
      if( not rc ) {
        rc = new segt( mid, rb );
      }
      rc->modify( k, v );
    }
    pull();
  }
  long long query( int k ) {
    if( lb + 1 == rb ) {
      return maxreach;
    }
    int mid = lb + rb >> 1;
    if( k < mid ) return lc->query( k );
    return rc->query( k );
  }
  int binsearch( int g ) {
    if( lb + 1 == rb ) {
      return lb;
    }
    int mid = lb + rb >> 1;
    if( lc and lc->maxreach >= g ) {
      return lc->binsearch( g );
    } else if( rc and rc->maxreach >= g and mid <= g ) {
      return rc->binsearch( g );
    }
    return -1;
  }
} *root = new segt( 0, MAXX + 1 );

unordered_map< int, int > eaten;
multiset< pair< int, int > > mosq;

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ) {
    cin >> X[ i ] >> T[ i ];
    root->modify( X[ i ], X[ i ] + T[ i ] );
  }
  for( int i = 0; i < M; ++i ) {
    int P, B;
    cin >> P >> B;
    int fp = root->binsearch( P );
    if( fp == -1 ) {
      mosq.emplace( P, B );
      continue;
    }
    ++eaten[ fp ];
    long long r = root->query( fp ) + B;
    for( auto it = mosq.lower_bound( make_pair( fp, 0 ) ); it != mosq.end(); ) {
      int p, b;
      tie( p, b ) = *it;
      if( p <= r ) {
        it = mosq.erase( it );
        r += b;
        ++eaten[ fp ];
      } else {
        break;
      }
    }
    root->modify( fp, r );
  }
  for( int i = 0; i < N; ++i ) {
    cout << eaten[ X[ i ] ] << " " << root->query( X[ i ] ) - X[ i ] << "\n";
  }
  return 0;
}