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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3526: [Poi2014]Card(线段树)  

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

  下载LOFTER 我的照片书  |

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=3526


假如不带修改,可以直接扫一遍解决,但是这个不好动态维护,我们发现分治同样可以解决这个问题,相当维护一下左边两个数到右边两个数是否可行,然后这样可以方便的线段树了,但是这样还是有点慢,考虑到左边的数固定的话,右边对应的数要越小越好,那么对于一个区间[l,r]维护一下l两个数对应的右边的数的最小值即可,如果不可行就正无穷表示,线段树上直接修改。。。没了


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •  

  • using namespace std ;

  •  

  • const int inf = 0x7fffffff ;

  • const int maxn = 201000 ;

  •  

  • int a[ maxn ][ 2 ] ;

  •  

  • struct node {

  •         node *lc , *rc ;

  •         int l , r , mid , c[ 2 ] ;

  •         inline void update(  ) {

  •                 c[ 0 ] = c[ 1 ] = inf ;

  •                 if ( lc -> c[ 0 ] <= a[ mid + 1 ][ 0 ] ) c[ 0 ] = min( c[ 0 ] , rc -> c[ 0 ] ) ;

  •                 if ( lc -> c[ 0 ] <= a[ mid + 1 ][ 1 ] ) c[ 0 ] = min( c[ 0 ] , rc -> c[ 1 ] ) ;

  •                 if ( lc -> c[ 1 ] <= a[ mid + 1 ][ 0 ] ) c[ 1 ] = min( c[ 1 ] , rc -> c[ 0 ] ) ;

  •                 if ( lc -> c[ 1 ] <= a[ mid + 1 ][ 1 ] ) c[ 1 ] = min( c[ 1 ] , rc -> c[ 1 ] ) ;

  •         }

  • } sgt[ maxn << 1 ] ;

  •  

  • node *pt = sgt , *root ;

  •  

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

  •         t = pt ++ ;

  •         t -> l = l , t -> r = r ;

  •         if ( l == r ) {

  •                 t -> c[ 0 ] = a[ l ][ 0 ] , t -> c[ 1 ] = a[ l ][ 1 ] ; return ;

  •         }

  •         t -> mid = ( l + r ) >> 1 ;

  •         build( l , t -> mid , t -> lc ) , build( t -> mid + 1 , r , t -> rc ) ;

  •         t -> update(  ) ;

  • }

  •  

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

  •         if ( t -> l == t -> r ) {

  •                 t -> c[ 0 ] = a[ t -> l ][ 0 ] , t -> c[ 1 ] = a[ t -> l ][ 1 ] ; return ;

  •         }

  •         change( x , x <= t -> mid ? t -> lc : t -> rc ) ;

  •         t -> update(  ) ;

  • }

  •  

  • 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 n , m ;

  •  

  • int main(  ) {

  •         getint( n ) ;

  •         for ( int i = 0 ; i ++ < n ; ) getint( a[ i ][ 0 ] ) , getint( a[ i ][ 1 ] ) ;

  •         build( 1 , n , root ) ;

  •         getint( m ) ;

  •         while ( m -- ) {

  •                 int x , y ; getint( x ) , getint( y ) ;

  •                 swap( a[ x ][ 0 ] , a[ y ][ 0 ] ) , swap( a[ x ][ 1 ] , a[ y ][ 1 ] ) ;

  •                 change( x , root ) , change( y , root ) ;

  •                 printf( min( root -> c[ 0 ] , root -> c[ 1 ] ) < inf ? "TAK\n" : "NIE\n" ) ;

  •         }

  •         return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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