Codeforces1045G

---

做法：按半徑r從大到小枚舉，對(duì)于每個(gè)q，枚舉對(duì)應(yīng)位置可能的q值，對(duì)每個(gè)q，維護(hù)出現(xiàn)的坐標(biāo)x，每次查詢半徑內(nèi)的已經(jīng)出現(xiàn)的坐標(biāo)的數(shù)目即可。需要實(shí)現(xiàn)一個(gè)插入單點(diǎn)加，查詢區(qū)間和的操作，動(dòng)態(tài)開點(diǎn)線段樹即可。看來還是要學(xué)習(xí)一下pb_ds了。

#include <bits/stdc++.h> typedef long long ll; const int N = 1e5 + 7; const ll lim = 1e9 + 7; inline int read() {char c = getchar(); int x = 0, f = 1;while( ! isdigit(c) ) { if(c == '-') f = -1; c = getchar(); }while( isdigit(c) ) { x = x*10 + c - '0'; c = getchar(); }return x * f; } inline void write( ll x ) {if( x >= 10 ) write( x / 10 );putchar( x % 10 + '0' ); } using namespace std; int n , k; ll ans = 0; struct node { ll x , r , q; } a[N]; bool cmp( node a , node b ) { return a.r > b.r; } set< ll > hv; struct Tree {int lson , rson; ll sum; }T[ N * 100 ]; map< ll , int > rt; int cnt = 0; void ins( int &rt , ll l , ll r , ll p ) {if( ! rt ) rt = ++ cnt;++ T[ rt ].sum;if( l == r ) return;ll mid = ( l + r ) >> 1;if( p <= mid ) ins( T[ rt ].lson , l , mid , p);else ins( T[ rt ].rson , mid + 1 , r , p ); } ll ask( int rt , ll l , ll r , ll p ) {if( ! rt ) return 0;if( r <= p ) return T[ rt ].sum;ll mid = ( l + r ) >> 1;if( p <= mid ) return ask( T[rt].lson , l , mid , p );else if( p > mid ) return T[ T[ rt ].lson ].sum + ask( T[rt].rson , mid + 1 , r , p ); } int main() {n = read(), k = read();for ( int i = 1 ; i <= n ; ++ i ) {a[ i ].x = read() , a[ i ].r = read() , a[ i ].q = read();hv.insert( a[ i ].q );}sort(a + 1 , a + n + 1 , cmp );int p = 0;for ( int i = 1 ; i <= n ; ++ i ) {for ( ll t = a[ i ].q - k; t <= a[ i ].q + k ; ++ t)if( hv.find(t) != hv.end() ) {ans += ask( rt[t] , 0 , lim , a[ i ].x + a[ i ].r );ans -= ask( rt[t] , 0 , lim , a[ i ].x - a[ i ].r - 1);}ins( rt[a[ i ].q] , 0 , lim , a[i].x );}write( ans ); putchar( '\n' );return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/RRRR-wys/p/9727342.html

總結(jié)

以上是生活随笔為你收集整理的Codeforces1045G的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。