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

GreenCloudS

 
 
 

日志

 
 

2724: [Violet 6]蒲公英(分块)  

2014-01-25 17:56:00|  分类: 分块,数据结构,bz |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


大意:区间众数,强制在线。至于题解,Violet6的解题报告已经够详细的了,就不班门弄斧了额。


代码(我写的是第二种写法O(n sqrt(n) log n),结果无限TLE,在N次常数优化之后终于AC了饿):

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

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

  • #define MAXN 40100

  • #define inf 0x7fffffff

  • #define MAXB 410

  • #define check( ch ) ( ch >= '0' && ch <= '9' )

  •  

  • void getint( int &t ) {

  •     int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;

  •     t = ch - '0' ;

  •     for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) {

  •         t *= 10 ; t += ch - '0' ;

  •     }

  • }

  •  

  • int w[ 20 ] ;

  •  

  • void putint( int t ) {

  •     if ( ! t ) putchar( '0' ) ; else {

  •         w[ 0 ] = 0 ;

  •         for ( ; t ; t /= 10 ) w[ ++ w[ 0 ] ] = t % 10 ;

  •         while ( w[ 0 ] -- ) putchar( '0' + w[ w[ 0 ] + 1 ] ) ;

  •     }

  •     putchar( '\n' ) ;

  • }

  •  

  • struct saver {

  •     int v , t ;

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

  •         return v < a.v || ( v == a.v && t < a.t ) ;

  •     }

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

  •         return v == a.v && t == a.t ;

  •     }

  •     bool operator > ( const saver &a ) const {

  •         return v > a.v || ( v == a.v && t > a.t ) ;

  •     }

  • } b[ MAXN ] ;

  •  

  • int N , first[ MAXN ] , last[ MAXN ] , Mn ;

  •  

  • saver make( int v , int t ) {

  •     saver u ;

  •     u.v = v , u.t = t ;

  •     return u ;

  • }

  •  

  • int Lower( int l , int r , saver v ) {

  •     l -- , ++ r ;

  •     while ( r - l > 1 ) {

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

  •         if ( b[ mid ] < v ) l = mid ; else r = mid ;

  •     }

  •     return r ;

  • }

  •  

  • int Upper( int l , int r , saver v ) {

  •     l -- , ++ r ;

  •     while ( r - l > 1 ) {

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

  •         if ( b[ mid ] > v ) r = mid ; else l = mid ;

  •     }

  •     return r ;

  • }

  •  

  • int COUNT( int l , int r , int v , int L , int R ) {

  •     return Upper( L , R , make( v , r ) ) - Lower( L , R , make( v , l ) ) ;

  • }

  •  

  • int n , m , M , a[ MAXN ] ;

  •  

  • int Begin[ MAXB ] , End[ MAXB ] , Ans[ MAXB ][ MAXB ] ;

  •  

  • void INIT(  ) {

  •     int ret = int( sqrt( n ) ) ;

  •     rep( i , ret ) {

  •         Begin[ i ] = ( i - 1 ) * ret + 1 ;

  •         End[ i ] = i * ret ;

  •     }

  •     if ( ret * ret < n ) {

  •         M = ret + 1 ;

  •         Begin[ M ] = ret * ret + 1 ;

  •         End[ M ] = n ;

  •     } else M = ret ;

  •     rep( i , M ) {

  •         int ans , rec = - inf ;

  •         for ( int j = i ; j <= M ; ++ j ) {

  •             for ( int k = Begin[ j ] ; k <= End[ j ] ; ++ k ) {

  •                 int cnt = COUNT( Begin[ i ] , k , a[ k ] , first[ k ] , last[ k ] ) ;

  •                 if ( cnt > rec || ( cnt == rec && a[ k ] < ans ) ) {

  •                     ans = a[ k ] , rec = cnt ;

  •                 }

  •             }

  •             Ans[ i ][ j ] = ans ;

  •         }

  •     }

  • }

  •  

  • int Query( int l , int r ) {

  •     int ans = 0 , rec = - inf , L , R , ret = int( sqrt( n ) ) ;

  •     L = ( l - 1 ) / ret + 1 , R = ( r - 1 ) / ret + 1 ;

  •     if ( L + 1 <= R - 1 ) {

  •             if ( ans == Ans[ L + 1 ][ R - 1 ] ) return ans ;

  •             int cnt = COUNT( l , r , Ans[ L + 1 ][ R - 1 ] , 1 , N ) ;

  •             if ( cnt > rec || ( cnt == rec && Ans[ L + 1 ][ R - 1 ] < ans ) ) {

  •                 rec = cnt , ans = Ans[ L + 1 ][ R - 1 ] ;

  •             }

  •         }

  •     if ( L == R ) {

  •         for ( int i = l ; i <= r ; ++ i ) {

  •             if ( a[ i ] == ans ) continue ;

  •             int cnt = COUNT( l , r , a[ i ] , first[ i ] , last[ i ] ) ;

  •             if ( cnt > rec || ( cnt == rec && a[ i ] < ans ) ) {

  •                 rec = cnt , ans = a[ i ] ;

  •             }

  •         }

  •     } else {

  •         for ( int i = l ; i <= End[ L ] ; ++ i ) {

  •             if ( a[ i ] == ans ) continue ;

  •             int cnt = COUNT( l , r , a[ i ] , first[ i ] , last[ i ] ) ;

  •             if ( cnt > rec || ( cnt == rec && a[ i ] < ans ) ) {

  •                 rec = cnt , ans = a[ i ] ;

  •             }

  •         }

  •         for ( int i = Begin[ R ] ; i <= r ; ++ i ) {

  •             if ( a[ i ] == ans ) continue ;

  •             int cnt = COUNT( l , r , a[ i ] , first[ i ] , last[ i ] ) ;

  •             if ( cnt > rec || ( cnt == rec && a[ i ] < ans ) ) {

  •                 rec = cnt , ans = a[ i ] ;

  •             }

  •         }

  •     }

  •     return ans ;

  • }

  •  

  • int main(  ) {

  •     getint( n ) , getint( m ) ;

  •     rep( i , n ) {

  •         getint( a[ i ] ) ;

  •         b[ i ].v = a[ i ] , b[ i ].t = i ;

  •     }

  •     N = n + 2 ;

  •     b[ n + 1 ].v = 0 , b[ n + 1 ].t = 0 ;

  •     b[ N ].v = inf , b[ N ].t = inf ;

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

  •     for ( int i = 0 ; i ++ < N ; ) {

  •         if ( i == 1 || b[ i ].v != b[ i - 1 ].v ) Mn = i ;

  •         first[ b[ i ].t ] = Mn ;

  •     }

  •     for ( int i = N ; i ; -- i ) {

  •         if ( i == N || b[ i ].v != b[ i + 1 ].v ) Mn = i ;

  •         last[ b[ i ].t ] = Mn ;

  •     }

  •     INIT(  ) ;

  •     int ans = 0 ;

  •     while ( m -- ) {

  •         int l , r ; getint( l ) , getint( r ) ;

  •         l = ( l + ans - 1 ) % n + 1 , r = ( r + ans - 1 ) % n + 1 ;

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

  •         putint( ans = Query( l , r ) ) ;

  •     }

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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