题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2105
CQF原题：http://wenku.baidu.com/view/1741543f5727a5e9856a6108.html
这道题网上的代码基本都是块状链表的，据说写SPLAY会T得很惨，然后我就各种DT地写了SBT，一交上去，TLE，然后回过头了，开始了漫长的常数优化，平衡化建树神马的都用上了，终于让我给卡过去了。。。
代码（在巨慢无比的时耗之后巨长无比的代码）：
63d0f703918fa0ec7beceb57249759ee3d6ddb45.jpg.png
#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 ;
}
网友评论