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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2821: 作诗(Poetize)(分块+二分)  

2014-02-20 18:50:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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


我这道题借鉴了一下2741的做法,先分成sqrt(n)块,对于每块的最后一个点x,预处理出每个x到后面位置的答案,然后对于一个询问[l,r],就拆成[l,x)+[x,r],[x,r]的内容已经预处理出,然后枚举[l,x)里的每一个权值,用二分查找进行统计,然后分类讨论即可。


代码:

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  • #include <cmath>

  •  

  • using namespace std ;

  •  

  • #define maxn 100001

  • #define maxc 100001

  • #define maxb 320

  • #define inf 0x7fffffff

  •  

  • 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 * 3 ] ;

  •  

  • saver make( int v , int t ) {

  •     saver u ;

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

  •     return u ;

  • }

  •  

  • int bn = 0 ;

  •  

  • int n , m , c , a[ maxn ] , left[ maxc ] , right[ maxc ] ;

  •  

  • void Init(  ) {

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

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

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

  •         b[ ++ bn ] = make( a[ i ] , i ) ;

  •     }

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

  •         b[ ++ bn ] = make( i , 0 ) ;

  •         b[ ++ bn ] = make( i , inf ) ;

  •     }

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

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

  •         if ( ! b[ i ].t ) left[ b[ i ].v ] = i ;

  •         if ( b[ i ].t == inf ) right[ b[ i ].v ] = i ;

  •     }

  • }

  •  

  • int R[ maxb ][ maxn ] , num[ maxn ] , p[ maxb ] , cnt[ maxc ] ;

  • int len , N ;

  •  

  • void Divide(  ) {

  •     len = int( sqrt( n ) ) ;

  •     N = 0 , p[ 0 ] = 0 ;

  •     memset( num , 0 , sizeof( num ) ) ;

  •     for ( int i = len ; i <= n ; i += len ) {

  •         p[ ++ N ] = i ;

  •         for ( int j = i ; j > p[ N - 1 ] ; -- j ) num[ j ] = N ;

  •     }

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

  •         for ( int j = 0 ; j ++ < c ; ) cnt[ j ] = 0 ;

  •         int ret = 0 ;

  •         for ( int j = p[ i ] ; j <= n ; ++ j ) {

  •             if ( cnt[ a[ j ] ] ) {

  •                 if ( cnt[ a[ j ] ] % 2 ) ++ ret ;

  •                 else -- ret ;

  •             }

  •             ++ cnt[ a[ j ] ] , R[ i ][ j ] = ret ;

  •         }

  •     }

  • }

  •  

  • int upper( saver x ) {

  •     int l = left[ x.v ] , r = right[ x.v ] ;

  •     while ( r - l > 1 ) {

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

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

  •     }

  •     return l ;

  • }

  •  

  • int lower( saver x ) {

  •     int l = left[ x.v ] , r = right[ x.v ] ;

  •     while ( r - l > 1 ) {

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

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

  •     }

  •     return l ;

  • }

  •  

  • int counter( int l , int r , int v ) {

  •     return upper( make( v , r ) ) - lower( make( v , l ) ) ;

  • }

  •  

  • int Index = 0 ;

  •  

  • int query( int l , int r ) {

  •     ++ Index ;

  •     if ( num[ l ] == num[ r ] ) {

  •         int ret = 0 ;

  •         for ( int i = l ; i <= r ; ++ i ) if ( cnt[ a[ i ] ] < Index ) {

  •             cnt[ a[ i ] ] = Index ;

  •             int cn = counter( l , r , a[ i ] ) ;

  •             if ( ! ( cn % 2 ) ) ++ ret ;

  •         }

  •         return ret ;

  •     } else {

  •         int pos = p[ num[ l ] ] ;

  •         int ret = R[ num[ l ] ][ r ] ;

  •         for ( int i = l ; i < pos ; ++ i ) if ( cnt[ a[ i ] ] < Index ) {

  •             cnt[ a[ i ] ] = Index ;

  •             int cnt0 = counter( l , pos - 1 , a[ i ] ) ;

  •             int cnt1 = counter( pos , r , a[ i ] ) ;

  •             if ( cnt1 ) {

  •                 if ( cnt0 % 2 ) {

  •                     if ( cnt1 % 2 ) ++ ret ; else -- ret ;

  •                 }

  •             } else if ( cnt0 && ! ( cnt0 % 2 ) ) ++ ret ;

  •         }

  •         return ret ;

  •     }

  • }

  •  

  • void Solve(  ) {

  •     memset( cnt , 0 , sizeof( cnt ) ) ;

  •     int ans = 0 ;

  •     while ( m -- ) {

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

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

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

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

  •     }

  • }

  •  

  • int main(  ) {

  •     Init(  ) ;

  •     Divide(  ) ;

  •     Solve(  ) ;

  •     return 0 ;

  • }



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

历史上的今天

评论

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

页脚

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