CFR 609 F. Frogs and mosquitoes ( Discretization, Segment Tree, Binary Search )
題意:
有 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; }