注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

GreenCloudS

 
 
 

日志

 
 

BZOJ-2716: [Violet 3]天使玩偶 && BZOJ-2648: SJY摆棋子(k-d树)  

2014-07-08 20:41:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

题目:

http://www.lydsy.com/JudgeOnline/problem.php?id=2648

http://www.lydsy.com/JudgeOnline/problem.php?id=2716


嘛。。。其实2716可以CDQ分治+BIT或者树套树水掉的,无奈代码量太大不敢写,于是就去搞了k-d树。。。结果搞了整整一天才调好。。。(偷懒的后果。。。)(话说BZOJ终于破500了好开心!~~)


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  • #include <cstdlib>

  • #include <map>

  •  

  • using namespace std ;

  •  

  • #define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

  • #define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

  • #define Rep( i , x ) for ( int i = 0 ; i < x ; ++ i )

  •  

  • const int inf = 0x7fffffff ;

  • const int maxn = 510000 ;

  • const int maxm = 510000 ;

  • const int maxv = 510000 + maxm ;

  •  

  • struct node {

  •     node *lc , *rc ;

  •     bool tag , Tag ;

  •     int x , y , flag , mx[ 2 ] , mn[ 2 ] ;

  •     node(  ) {

  •         lc = rc = NULL , tag = Tag = false ;

  •     }

  • } kdt[ maxv ] ;

  •  

  • node *pt = kdt , *root ;

  •  

  • struct point {

  •     int x , y ;

  •     inline void oper( int _x , int _y ) {

  •         x = _x , y = _y ;

  •     }

  •     bool operator < ( const point &a ) const {

  •         return x < a.x || ( x == a.x && y < a.y ) ;

  •     }

  •     bool operator == ( const point &a ) const {

  •         return x == a.x && y == a.y ;

  •     }

  •     bool operator != ( const point &a ) const {

  •         return x != a.x || y != a.y ;

  •     }

  • } p[ maxn + maxm ] , b[ maxn + maxm ] ;

  •  

  • int n , m , q[ maxm ][ 3 ] , cnt , N = 0 , a[ maxn ][ 2 ] ;

  •  

  • void Selectx( int l , int r , int k ) {

  •     if ( l >= r ) return ;

  •     int i = l , j = r , x = b[ ( l + r ) >> 1 ].x ;

  •     do {

  •         for ( ; b[ i ].x < x ; ++ i ) ;

  •         for ( ; b[ j ].x > x ; -- j ) ;

  •         if ( i <= j ) swap( b[ i ++ ] , b[ j -- ] ) ;

  •     } while ( i <= j ) ;

  •     if ( i < r && k >= i && k <= r ) Selectx( i , r , k ) ;

  •     if ( j > l && k >= l && k <= j ) Selectx( l , j , k ) ;

  • }

  •  

  • void Selecty( int l , int r , int k ) {

  •     if ( l >= r ) return ;

  •     int i = l , j = r , y = b[ ( l + r ) >> 1 ].y ;

  •     do {

  •         for ( ; b[ i ].y < y ; ++ i ) ;

  •         for ( ; b[ j ].y > y ; -- j ) ;

  •         if ( i <= j ) swap( b[ i ++ ] , b[ j -- ] ) ;

  •     } while ( i <= j ) ;

  •     if ( i < r && k >= i && k <= r ) Selecty( i , r , k ) ;

  •     if ( j > l && k >= l && k <= j ) Selecty( l , j , k ) ;

  • }

  •  

  • void build( int l , int r , bool flag , node* &t ) {

  •     if ( l > r ) return ;

  •     t = pt ++ ;

  •     int mid = ( l + r ) >> 1 ;

  •     if ( t -> flag = flag ) Selectx( l , r , mid ) ; else Selecty( l , r , mid ) ;

  •     t -> x = b[ mid ].x , t -> y = b[ mid ].y ;

  •     int _l = l , _r = r ;

  •     if ( flag ) {

  •         while ( _l < _r ) {

  •             for ( ; b[ _l ].x <= t -> x && _l <= r ; ++ _l ) ;

  •             for ( ; b[ _r ].x > t -> x && _r >= l ; -- _r ) ;

  •             if ( _l < _r ) swap( b[ _l ++ ] , b[ _r -- ] ) ;

  •         }

  •         for ( _l = l ; b[ _l + 1 ].x <= t -> x && _l < r ; ++ _l ) ;

  •         REP( i , l , ( _l - 1 ) ) if ( b[ i ].x == t -> x && b[ i ].y == t -> y ) {

  •             swap( b[ i ] , b[ _l ] ) ; break ;

  •         }

  •     } else {

  •         while ( _l < _r ) {

  •             for ( ; b[ _l ].y <= t -> y && _l <= r ; ++ _l ) ;

  •             for ( ; b[ _r ].y > t -> y && _r >= l ; -- _r ) ;

  •             if ( _l < _r ) swap( b[ _l ++ ] , b[ _r -- ] ) ;

  •         }

  •         for ( _l = l ; b[ _l + 1 ].y <= t -> y && _l < r ; ++ _l ) ;

  •         REP( i , l , ( _l - 1 ) ) if ( b[ i ].x == t -> x && b[ i ].y == t -> y ) {

  •             swap( b[ i ] , b[ _l ] ) ; break ;

  •         }

  •     }

  •     t -> mn[ 0 ] = t -> mn[ 1 ] = inf , t -> mx[ 0 ] = t -> mx[ 1 ] = - inf ;

  •     REP( i , l , r ) {

  •         t -> mn[ 0 ] = min( t -> mn[ 0 ] , b[ i ].x ) ;

  •         t -> mn[ 1 ] = min( t -> mn[ 1 ] , b[ i ].y ) ;

  •         t -> mx[ 0 ] = max( t -> mx[ 0 ] , b[ i ].x ) ;

  •         t -> mx[ 1 ] = max( t -> mx[ 1 ] , b[ i ].y ) ;

  •     }

  •     build( l , _l - 1 , flag ^ true , t -> lc ) ;

  •     build( _l + 1 , r , flag ^ true , t -> rc ) ;

  • }

  •  

  • void change( int x , int y , node *t ) {

  •     t -> Tag = true ;

  •     if ( t -> x == x && t -> y == y ) {

  •         t -> tag = true ; return ;

  •     }

  •     if ( t -> flag ) {

  •         if ( x <= t -> x ) change( x , y , t -> lc ) ; else change( x , y , t -> rc ) ;

  •     } else {

  •         if ( y <= t -> y ) change( x , y , t -> lc ) ; else change( x , y , t -> rc ) ;

  •     }

  • }

  •  

  • int ans ;

  •  

  • void query( int x , int y , node *t ) {

  •     if ( ! t ) return ;

  •     if ( ! t -> Tag ) return ;

  •     if ( t -> tag ) ans = min( ans , abs( x - t -> x ) + abs( y - t -> y ) ) ;

  •     if ( ! ans ) return ;

  •     int d = 0 ;

  •     if ( x > t -> mx[ 0 ] ) d += x - t -> mx[ 0 ] ;

  •     if ( x < t -> mn[ 0 ] ) d += t -> mn[ 0 ] - x ;

  •     if ( y > t -> mx[ 1 ] ) d += y - t -> mx[ 1 ] ;

  •     if ( y < t -> mn[ 1 ] ) d += t -> mn[ 1 ] - y ;

  •     if ( d >= ans ) return ;

  •     if ( t -> flag ) {

  •         if ( x <= t -> x ) {

  •             query( x , y , t -> lc ) ;

  •             if ( t -> x + 1 - x < ans ) query( x , y , t -> rc ) ;

  •         } else {

  •             query( x , y , t -> rc ) ;

  •             if ( x - t -> x < ans ) query( x , y , t -> lc ) ;

  •         }

  •     } else {

  •         if ( y <= t -> y ) {

  •             query( x , y , t -> lc ) ;

  •             if ( t -> y + 1 - y < ans ) query( x , y , t -> rc ) ;

  •         } else {

  •             query( x , y , t -> rc ) ;

  •             if ( y - t -> y < ans ) query( x , y , t -> lc ) ;

  •         }

  •     }

  • }

  •  

  • int ch ;

  •  

  • inline void getint( int &t ) {

  •     for ( ch = getchar(  ) ; ch < '0' || ch > '9' ; ch = getchar(  ) ) ; t = ch - '0' ;

  •     for ( ch = getchar(  ) ; ch >= '0' && ch <= '9' ; ch = getchar(  ) ) t = t * 10 + ch - '0' ;

  • }

  •  

  • int main(  ) {

  •     getint( n ) , getint( m ) ;

  •     rep( i , n ) {

  •         getint( a[ i ][ 0 ] ) , getint( a[ i ][ 1 ] ) ;

  •         p[ i ].oper( a[ i ][ 0 ] , a[ i ][ 1 ] ) ;

  •     }

  •     cnt = n ;

  •     rep( i , m ) {

  •         getint( q[ i ][ 0 ] ) , getint( q[ i ][ 1 ] ) , getint( q[ i ][ 2 ] ) ;

  •         if ( q[ i ][ 0 ] == 1 ) p[ ++ cnt ].oper( q[ i ][ 1 ] , q[ i ][ 2 ] ) ;

  •     }

  •     sort( p + 1 , p + cnt + 1 ) ;

  •     rep( i , cnt ) if ( i == 1 || p[ i ] != p[ i - 1 ] ) b[ ++ N ] = p[ i ] ;

  •     random_shuffle( b + 1 , b + N + 1 ) ;

  •     build( 1 , N , true , root ) ;

  •     rep( i , n ) {

  •         change( a[ i ][ 0 ] , a[ i ][ 1 ] , root ) ;

  •     }

  •     rep( i , m ) if ( q[ i ][ 0 ] == 1 ) change( q[ i ][ 1 ] , q[ i ][ 2 ] , root ) ; else {

  •         ans = inf ; query( q[ i ][ 1 ] , q[ i ][ 2 ] , root ) ;

  •         printf( "%d\n" , ans ) ;

  •     }

  •     return 0 ;

  • }


  评论这张
 
阅读(5)| 评论(5)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017