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

GreenCloudS

 
 
 

日志

 
 

BZOJ-3489: A simple rmq problem(持久化二维线段树)  

2014-03-28 10:35:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


昨天脑子晒得有点残了,所以发上来的题解也相当暴力额。。

首先对于设位置在pos的数前面的第一个与他相同的数位置是pre(不存在则为0),后面第一个与他位置相同的数位置是suff(不存在则为n+1)的话,那么这题就是在找一个数对(pre,pos,suff)其中0<=pre<l  , l<=pos<=r  , r<suff<=n+1,且要求value(pos)最大,那么又考虑到pre是从0开始记的,那么我们就以pre建立一串类似前缀和的持久化二维线段树维护最大值即可。


代码(反正我写残了,基本就是卡着过掉的额):

BZOJ-3489: A simple rmq problem(持久化二维线段树) - cjjlsdy - cjjlsdy的博客

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <vector>

  •  

  • using namespace std ;

  •  

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

  •  

  • const int maxvx = 3001000 ;

  • const int maxvy = 40010000 ;

  • const int maxn = 100100 ;

  •  

  • struct point {

  •     int x , y ;

  •     point( int _x , int _y ) : x( _x ) , y( _y ) {

  •     }

  • };

  •  

  • struct nodey {

  •     int left , right , Max ;

  •     nodey(  ) {

  •         left = right = Max = 0 ;

  •     }

  • } sgty[ maxvy ] ;

  •  

  • struct nodex {

  •     int left , right , sgt ;

  •     nodex(  ) {

  •         left = right = sgt = 0 ;

  •     }

  • } sgtx[ maxvx ] ;

  •  

  • int vx = 0 , vy = 0 ;

  • int n , m , a[ maxn ] ;

  •  

  • void addy( int pos , int value , int l , int r , int u , int &t ) {

  •     if ( ! t ) t = ++ vy ;

  •     sgty[ t ].Max = max( sgty[ u ].Max , value ) ;

  •     if ( l == r ) return ;

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

  •     if ( pos <= mid ) {

  •         sgty[ t ].right = sgty[ u ].right ;

  •         addy( pos , value , l , mid , sgty[ u ].left , sgty[ t ].left ) ;

  •     } else {

  •         sgty[ t ].left = sgty[ u ].left ;

  •         addy( pos , value , mid + 1 , r , sgty[ u ].right , sgty[ t ].right ) ;

  •     }

  • }

  •  

  • int queryy( int l , int r , int _l , int _r , int t ) {

  •     if ( ! t ) return 0 ;

  •     if ( l == _l && r == _r ) return sgty[ t ].Max ;

  •     int mid = ( _l + _r ) >> 1 ;

  •     if ( r <= mid ) return queryy( l , r , _l , mid , sgty[ t ].left ) ;

  •     if ( l > mid ) return queryy( l , r , mid + 1 , _r , sgty[ t ].right ) ;

  •     return max( queryy( l , mid , _l , mid , sgty[ t ].left ) , queryy( mid + 1 , r , mid + 1 , _r , sgty[ t ].right ) ) ;

  • }

  •  

  • void addx( point pos , int value , int l , int r , int u , int &t ) {

  •     if ( ! t ) t = ++ vx ;

  •     addy( pos.y , value , 0 , n + 1 , sgtx[ u ].sgt , sgtx[ t ].sgt ) ;

  •     if ( l == r ) return ;

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

  •     if ( pos.x <= mid ) {

  •         sgtx[ t ].right = sgtx[ u ].right ;

  •         addx( pos , value , l , mid , sgtx[ u ].left , sgtx[ t ].left ) ;

  •     } else {

  •         sgtx[ t ].left = sgtx[ u ].left ;

  •         addx( pos , value , mid + 1 , r , sgtx[ u ].right , sgtx[ t ].right ) ;

  •     }

  • }

  •  

  • int queryx( point l , point r , int _l , int _r , int t ) {

  •     if ( ! t ) return 0 ;

  •     if ( l.x == _l && r.x == _r ) return queryy( l.y , r.y , 0 , n + 1 , sgtx[ t ].sgt ) ;

  •     int mid = ( _l + _r ) >> 1 ;

  •     if ( r.x <= mid ) return queryx( l , r , _l , mid , sgtx[ t ].left ) ;

  •     if ( l.x > mid ) return queryx( l , r , mid + 1 , _r , sgtx[ t ].right ) ;

  •     int templ = queryx( l , point( mid , r.y ) , _l , mid , sgtx[ t ].left ) ;

  •     int tempr = queryx( point( mid + 1 , l.y ) , r , mid + 1 , _r , sgtx[ t ].right ) ;

  •     return max( templ , tempr ) ;

  • }

  •  

  • struct Num {

  •     int pos , value ;

  •     void oper( int _pos , int _value ) {

  •         pos = _pos , value = _value ;

  •     }

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

  •         return value < a.value || ( value == a.value && pos < a.pos ) ;

  •     }

  • } b[ maxn << 2 ] ;

  •  

  • int N = 0 ;

  • vector < point > ve[ maxn ] ;

  • bool used[ maxn ] ;

  •  

  • typedef vector < point > :: iterator P ;

  •  

  • int Pre[ maxn ] ;

  •  

  • int query( int l , int r ) {

  •     return queryx( point( l , r + 1 ) , point( r , n + 1 ) , 1 , n , Pre[ l ] ) ;

  • }

  •  

  • int main(  ) {

  •     scanf( "%d%d" , &n , &m ) ;

  •     memset( used , false , sizeof( used ) ) ;

  •     rep( i , n ) {

  •         scanf( "%d" , a + i ) ;

  •         if ( ! used[ a[ i ] ] ) {

  •             used[ a[ i ] ] = true ;

  •             b[ ++ N ].oper( 0 , a[ i ] ) ;

  •             b[ ++ N ].oper( n + 1 , a[ i ] ) ;

  •         }

  •         b[ ++ N ].oper( i , a[ i ] ) ;

  •     }

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

  •     rep( i , N ) if ( i > 1 && i < N && b[ i ].value == b[ i - 1 ].value && b[ i ].value == b[ i + 1 ].value ) {

  •         ve[ b[ i - 1 ].pos + 1 ].push_back( point( b[ i ].pos , b[ i + 1 ].pos ) ) ;

  •     }

  •     Pre[ 0 ] = 0 ;

  •     rep( i , n ) {

  •         Pre[ i ] = Pre[ i - 1 ] ;

  •         int temp ;

  •         for ( P p = ve[ i ].begin(  ) ; p != ve[ i ].end(  ) ; ++ p ) {

  •             temp = 0 ;

  •             addx( *p , a[ p -> x ] , 1 , n , Pre[ i ] , temp ) ;

  •             Pre[ i ] = temp ;

  •         }

  •     }

  •     int last = 0 ;

  •     while ( m -- ) {

  •         int x , y , l , r ; scanf( "%d%d" , &x , &y ) ;

  •         l = ( x + last ) % n + 1 , r = ( y + last ) % n + 1 ;

  •         if ( l > r ) swap( l , r ) ;

  •         printf( "%d\n" , last = query( l , r ) ) ;

  •     }

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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