【COGS】256 [POI2001] 金矿 线段树

本文主要是介绍【COGS】256 [POI2001] 金矿 线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【COGS】256 [POI2001] 金矿

题目分析：将每个点作为一个矩阵的右下角添加这个矩阵的下边以及上边，这样本题转化成了区间加减以及求区间最大的问题。

代码如下：

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define root 1 , 1 , cnt
#define mid ( ( l + r ) >> 1 )const int MAXN = 15005 ;struct Line {int l , r , h , v ;Line () {}Line ( int l , int r , int h , int v ) : l ( l ) , r ( r ) , h ( h ) , v ( v ) {}bool operator < ( const Line& a ) const {return h != a.h ? h < a.h : v > a.v ;}
} L[MAXN << 1] ;int a[MAXN << 1] , cnt ;
int maxv[MAXN << 3] , addv[MAXN << 3] ;
int s , w ;
int n ;void scanf ( int& x , char c = 0 , bool flag = 0 ) {while ( ( c = getchar () ) != '-' && ( c < '0' || c > '9' ) ) ;if ( c == '-' ) flag = 1 , x = 0 ;else x = c - '0' ;while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;if ( flag ) x = -x ;
}int unique ( int n ) {int cnt = 1 ;sort ( a + 1 , a + n + 1 ) ;FOR ( i , 2 , n ) if ( a[i] != a[cnt] ) a[++ cnt] = a[i] ;return cnt ;
}int search ( int x , int l , int r ) {while ( l < r ) {int m = mid ;if ( a[m] >= x ) r = m ;else l = m + 1 ;}return l ;
}void pushdown ( int o ) {if ( addv[o] ) {addv[ls] += addv[o] ;addv[rs] += addv[o] ;maxv[ls] += addv[o] ;maxv[rs] += addv[o] ;addv[o] = 0 ;}
}void update ( int L , int R , int v , int o , int l , int r ) {if ( L <= l && r <= R ) {maxv[o] += v ;addv[o] += v ;return ;}int m = mid ;pushdown ( o ) ;if ( L <= m ) update ( L , R , v , lson ) ;if ( m <  R ) update ( L , R , v , rson ) ;maxv[o] = max ( maxv[ls] , maxv[rs] ) ;
}void solve () {int x , y ;scanf ( s ) ;scanf ( w ) ;scanf ( n ) ;cnt = 0 ;CLR ( addv , 0 ) ;CLR ( maxv , 0 ) ;REP ( i , 0 , n ) {scanf ( "%d%d" , &x , &y ) ;a[++ cnt] = x ;a[++ cnt] = x + s ;L[i << 1] = Line ( x , x + s , y , 1 ) ;L[i << 1 | 1] = Line ( x , x + s , y + w , -1 ) ;}cnt = unique ( cnt ) ;n <<= 1 ;sort ( L , L + n ) ;int ans = 0 ;REP ( i , 0 , n ) {int l = search ( L[i].l , 1 , cnt ) ;int r = search ( L[i].r , 1 , cnt ) ;update ( l , r , L[i].v , root ) ;ans = max ( ans , maxv[1] ) ;}printf ( "%d\n" , ans ) ;
}int main () {freopen ( "kop.in" , "r" , stdin ) ;freopen ( "kop.out" , "w" , stdout ) ;solve () ;return 0 ;
}

这篇关于【COGS】256 [POI2001] 金矿 线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---