题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1014
这道题是有修改的,那么SA就不行了,想想之前那个字符串HASH的LCP求法,令hash(i,j)=s(j)27^0+s(j-1)27^1+...+s(i)*(j-i),那么如果hash(i,j)=hash(l,r),那么说明s(i..j)与s(l..r)有很高的概率相同,那么用splay维护hash,然后二分查找判定即可求出LCP。(虽然我不太喜欢字符串HASH这种不是100%的算法就是了,为了不被专门的数据卡WA,建议多取一两个HASH值进行比较)(这道题取26来乘就会WA。。。QaQ...)。
代码(觉得这种题还是递归版splay好写多了):
77094b36acaf2edd2f51958a8f1001e939019335.jpg.png#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std ;
#define MAXN 300100
#define L( t ) left[ t ]
#define R( t ) right[ t ]
#define S( t ) size[ t ]
#define H( t ) Hash[ t ]
#define V( t ) value[ t ]
#define C( t )( t ==L(F( t )))
#define ULL unsigned long long
int getstr(char*s ){
int len =0, ch ;
for( ch =getchar( );!( ch >='a'&& ch <='z'); ch =getchar( ));
s[++ len ]= ch ;
for( ch =getchar( ); ch >='a'&& ch <='z'; ch =getchar( )) s[++ len ]= ch ;
return len ;
}
char getchr( ){
int ch ;for( ch =getchar( );!(( ch >='A'&& ch <='Z')||( ch >='a'&& ch <='z')); ch =getchar( ));
return ch ;
}
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';
}
}
void putint(int t ){
if(! t )putchar('0');else{
int ans[20]; ans[0]=0;
for(; t ; t /=10) ans[++ ans[0]]= t %10;
for(int i = ans[0]; i ; i --)putchar('0'+ ans[ i ]);
}
putchar('\n');
}
int left[ MAXN ], right[ MAXN ], size[ MAXN ];
ULL Hash[ MAXN ], value[ MAXN ], Exp[ MAXN ];
int roof =0, V =0;
void update(int t ){
S( t )=S(L( t ))+S(R( t ))+1;
H( t )=H(R( t ));
H( t )+=V( t )* Exp[S(R( t ))];
H( t )+=H(L( t ))* Exp[S(R( t ))+1];
}
void zag(int&t ){
int k =R( t );
R( t )=L( k );update( t );
L( k )= t ;update( k );
t = k ;
}
void zig(int&t ){
int k =L( t );
L( t )=R( k );update( t );
R( k )= t ;update( k );
t = k ;
}
bool splay(int r ,int&t ,bool flag ){
if(S(L( t ))== r )return true;
bool w =splay( r <S(L( t ))? r : r -S(L( t ))-1, r <S(L( t ))?L( t ):R( t ),false);
if(! w ){
if( r <S(L( t ))){
if( r <S(L(L( t ))))zig( t );else zag(L( t ));
zig( t );
}else{
r -=S(L( t )),-- r ;
if( r <S(L(R( t ))))zig(R( t ));else zag( t );
zag( t );
}
}else if( flag ){
if( r <S(L( t )))zig( t );else zag( t );
}
return w ^true;
}
void Insert(int k ,int&t ){
if(! t ){
t =++ V ;
L( t )=R(0)=0;
V( t )=H( t )= k ;
S( t )=1;
return;
}
Insert( k ,R( t ));
update( t );
}
char s[ MAXN ];
int n , m ;
void Init( ){
Exp[0]=1;
for(int i =0; i ++< n + m ;) Exp[ i ]= Exp[ i -1]*27;
L(0)=R(0)=S(0)=0,V(0)=H(0)=0;
Insert(0, roof );
for(int i =0; i ++< n ;){
Insert(int( s[ i ])-int('0'), roof );
splay(S( roof )-1, roof ,true);
}
Insert(0, roof );
}
ULL cp(int l ,int r ){
splay( l -1, roof ,true);
splay( r - l +1,R( roof ),true);
return H(L(R( roof )));
}
int Query(int x ,int y ){
if( x > y )swap( x , y );
int len =S( roof )-2;
int l =0, r = len - y +2;
while( r - l >1){
int mid =( l + r )>>1;
if(cp( x , x + mid -1)==cp( y , y + mid -1)) l = mid ;else r = mid ;
}
return l ;
}
int main( ){
n =getstr( s );getint( m );
Init( );
while( m --){
char c =getchr( );
if( c =='Q'){
int x , y ;getint( x ),getint( y );
putint(Query( x , y ));
}else if( c =='R'){
int x ;getint( x ); c =getchr( );
splay( x , roof ,true);
V( roof )= c -'0';
update( roof );
}else{
int x ;getint( x ); c =getchr( );
splay( x , roof ,true);
splay(0,R( roof ),true);
Insert(int( c )-int('0'),L(R( roof )));
update(R( roof ));update( roof );
}
}
return 0;
}
网友评论