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

GreenCloudS

 
 
 

日志

 
 

BZOJ-2105: 增强型LCP(HASH+SBT)  

2014-02-05 22:56:00|  分类: oi,bzoj,数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

CQF原题:http://wenku.baidu.com/view/1741543f5727a5e9856a6108.html


这道题网上的代码基本都是块状链表的,据说写SPLAY会T得很惨,然后我就各种DT地写了SBT,一交上去,TLE,然后回过头了,开始了漫长的常数优化,平衡化建树神马的都用上了,终于让我给卡过去了。。。


代码(在巨慢无比的时耗之后巨长无比的代码):

BZOJ-2105: 增强型LCP(HASH+SBT) - cjjlsdy - cjjlsdy的博客

  • #include <cstdio>

  • #include <algorithm>

  • #include <cstring>

  •   

  • using namespace std ;

  •   

  • #define L( t ) left[ t ]

  • #define R( t ) right[ t ]

  • #define S( t ) size[ t ]

  • #define V( t ) value[ t ]

  • #define H( t ) Hash[ t ]

  • #define MAXN 201000

  • #define ULL int

  • #define MAX 29

  • #define clear( x ) memset( x , 0 , sizeof( x ) )

  • #define check( ch ) ( ch >= 'A' && ch <= 'Z' )

  •   

  • int left[ MAXN ] , right[ MAXN ] , V = 0 , roof = 0 ;

  • ULL value[ MAXN ] , Hash[ MAXN ] , Exp[ MAXN ] , size[ MAXN ] ;

  •   

  • void update( int t ) {

  •     S( t ) = S( L( t ) ) + S( R( t ) ) + 1 ;

  •     H( t ) = H( R( t ) ) + Exp[ S( R( t ) ) ] * V( t ) + Exp[ S( R( t ) ) + 1 ] * H( L( t ) ) ;

  • }

  •   

  • void Left( int &t ) {

  •     int k = R( t ) ;

  •     R( t ) = L( k ) ; update( t ) ;

  •     L( k ) = t ; update( k ) ;

  •     t = k ;

  • }

  •   

  • void Right( int &t ) {

  •     int k = L( t ) ;

  •     L( t ) = R( k ) ;update( t ) ;

  •     R( k ) = t ; update( k ) ;

  •     t = k ;

  • }

  •   

  • void maintain( int &t ) {

  •     if ( S( L( L( t ) ) ) > S( R( t ) ) ) {

  •         Right( t ) ;

  •         maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( R( L( t ) ) ) > S( R( t ) ) ) {

  •         Left( L( t ) ) ; Right( t ) ;

  •         maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( R( R( t ) ) ) > S( L( t ) ) ) {

  •         Left( t ) ;

  •         maintain( L( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  •     if ( S( L( R( t ) ) ) > S( L( t ) ) ) {

  •         Right( R( t ) ) ; Left( t ) ;

  •         maintain( L( t ) ) , maintain( R( t ) ) ; maintain( t ) ;

  •         return ;

  •     }

  • }

  •   

  • void Insert( int s , int u , int &t ) {

  •     if ( ! t ) {

  •         t = u ; return ;

  •     }

  •     if ( S( L( t ) ) >= s ) Insert( s , u , L( t ) ) ; else

  •     Insert( s - S( L( t ) ) - 1 , u , R( t ) ) ;

  •     update( t ) ; maintain( t ) ;

  • }

  •   

  • void Delete( int s , int &t ) {

  •     if ( s == S( L( t ) ) ) {

  •         if ( ! L( t ) ) {

  •             t = R( t ) ; return ;

  •         } else if ( ! R( t ) ) {

  •             t = L( t ) ; return ;

  •         } else {

  •             Right( t ) ; Delete( S( L( R( t ) ) ) , R( t ) ) ;

  •         }

  •     } else if ( s < S( L( t ) ) ) Delete( s , L( t ) ) ; else

  •     Delete( s - S( L( t ) ) - 1 , R( t ) ) ;

  •     update( t ) ; maintain( t ) ;

  • }

  •   

  • ULL Query( ULL l , ULL r , int t ) {

  •     if ( ! l && r == S( t ) - 1 ) return H( t ) ;

  •     if ( r < S( L( t ) ) ) return Query( l , r , L( t ) ) ;

  •     if ( l > S( L( t ) ) ) return Query( l - S( L( t ) ) - 1 , r - S( L( t ) ) - 1 , R( t ) ) ;

  •     if ( l == S( L( t ) ) && r == S( L( t ) ) ) return V( t ) ;

  •     if ( r == S( L( t ) ) ) {

  •         return Query( l , r - 1 , L( t ) ) * Exp[ 1 ] + V( t ) ;

  •     } else if ( l == S( L( t ) ) ) {

  •         return V( t ) * Exp[ r - l ] + Query( 0 , r - S( L( t ) ) - 1 , R( t ) ) ;

  •     } else {

  •         ULL x = Query( l , S( L( t ) ) - 1 , L( t ) ) ;

  •         ULL y = Query( 0 , r - S( L( t ) ) - 1 , R( t ) ) ;

  •         return x * Exp[ r - S( L( t ) ) + 1 ] + V( t ) * Exp[ r - S( L( t ) ) ] + y ;

  •     }

  • }

  •   

  • void create( char c , int t ) {

  •     S( t ) = 1 , V( t ) = H( t ) = c ;

  •     return ;

  • }

  •   

  • void INIT(  ) {

  •     clear( left ) , clear( right ) , clear( size ) ;

  •     clear( value ) , clear( Hash ) , clear( Exp ) ;

  •     Exp[ 0 ] = 1 ;

  •     for ( int i = 0 ; i ++ < MAXN - 1 ; ) Exp[ i ] = Exp[ i - 1 ] * MAX ;

  • }

  •   

  • char s[ MAXN ] ;

  • int n , m ;

  •   

  • int Solve( int x , int y ) {

  •     int l = 0 , r = min( S( roof ) - x + 1 , S( roof ) - y + 1 ) + 1 ;

  •     int lastmid = 0x7fffffff ;

  •     ULL lastrec , lastret ;

  •     while ( r - l > 1 ) {

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

  •         ULL rec , ret ;

  •         if ( lastmid < mid ) {

  •             rec = Query( x + lastmid - 1 , x + mid - 2 , roof ) ;

  •             ret = Query( y + lastmid - 1 , y + mid - 2 , roof ) ;

  •             rec = lastrec * Exp[ mid - lastmid ] + rec ;

  •             ret = lastret * Exp[ mid - lastmid ] + ret ;

  •         } else {

  •             rec = Query( x - 1 , x + mid - 2 , roof ) ;

  •             ret = Query( y - 1 , y + mid - 2 , roof ) ;

  •         }

  •         if ( rec == ret ) {

  •             l = mid ;

  •         } else r = mid ;

  •         lastmid = mid ;

  •         lastrec = rec , lastret = ret ;

  •     }

  •     return l ;

  • }

  •   

  • int getstr( char *ss ) {

  •     int ch , len = 0 ;

  •     for ( ch = getchar(  ) ; ch == ' ' || ch == '\n' || ch == EOF ; ch = getchar(  ) ) ;

  •     ss[ len ++ ] = ch ;

  •     for ( ch = getchar(  ) ; ch != ' ' && ch != '\n' && ch != EOF ; ch = getchar(  ) ) ss[ len ++ ] = ch ;

  •     return len ;

  • }

  •   

  • void getint( int &t ) {

  •     int ch ; for ( ch = getchar(  ) ; ! ( ch >= '0' && ch <= '9' ) ; ch = getchar(  ) ) ;

  •     t = ch - '0' ;

  •     for ( ch = getchar(  ) ; ch >= '0' && ch <= '9' ; ch = getchar(  ) ) {

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

  •     }

  • }

  •  

  • int out[ 20 ] ;

  •  

  • void putint( int t ) {

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

  •         out[ 0 ] = 0 ;

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

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

  •     }

  •     putchar( '\n' ) ;

  • }

  •  

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

  •     t = ++ V ;

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

  •     V( t ) = s[ mid ] , S( t ) = 1 ;

  •     if ( l <= mid - 1 ) build( l , mid - 1 , L( t ) , s ) ;

  •     if ( r >= mid + 1 ) build( mid + 1 , r , R( t ) , s ) ;

  •     update( t ) ;

  • }

  •  

  • void CHANGE( int l , int r , int l0 , int r0 , char *s , int t ) {

  •     if ( r < S( L( t ) ) ) CHANGE( l , r , l0 , r0 , s , L( t ) ) ; else

  •     if ( l > S( L( t ) ) ) CHANGE( l - S( L( t ) ) - 1 , r - S( L( t ) ) - 1 , l0 , r0 , s , R( t ) ) ; else {

  •         int L = S( L( t ) ) - l ;

  •         int R = r - l - L ;

  •         V( t ) = s[ l0 + L ] ;

  •         if ( L ) CHANGE( l , S( L( t ) ) - 1 , l0 , l0 + L - 1 , s , L( t ) ) ;

  •         if ( R ) CHANGE( 0 , r - S( L( t ) ) - 1 , r0 - R + 1 , r0 , s , R( t ) ) ;

  •     }

  •     update( t ) ;

  •      

  • }

  •  

  • int main(  ) {

  •     INIT(  ) ;

  •     getint( n ) , getint( m ) ;

  •     getstr( s ) ;

  •     build( 0 , n - 1 , roof , s ) ;

  •     while ( m -- ) {

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

  •         if ( ch == 'L' ) {

  •             int a , b ; getint( a ) , getint( b ) ;

  •             putint( Solve( a , b ) ) ;

  •         } else if ( ch == 'A' ) {

  •             int x ; getint( x ) ;

  •             int len = getstr( s ) ;

  •             int t = 0 ;

  •             build( 0 , len - 1 , t , s ) ;

  •             Insert( x - 1 , t , roof ) ;

  •         } else if ( ch == 'C' ) {

  •             int a , b ; getint( a ) , getint( b ) ;

  •             int len = getstr( s ) ;

  •             -- a , -- b ;

  •             CHANGE( a , b , 0 , len - 1 , s , roof ) ;

  •         } else if ( ch == 'D' ) {

  •             int a , b ; getint( a ) , getint( b ) ;

  •             for ( int i = a ; i <= b ; ++ i ) {

  •                 Delete( a - 1 , roof ) ;

  •             }

  •         }

  •     }

  •     return 0 ;

  • }


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

历史上的今天

评论

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

页脚

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