BZOJ-1014: [JSOI2008]火星人prefix（字

题目：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;

}