美文网首页信息学竞赛题解(IO题解)
BZOJ-1014: [JSOI2008]火星人prefix(字

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

作者: AmadeusChan | 来源:发表于2018-10-16 20:46 被阅读1次

    题目: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;
    
    }
    

    相关文章

      网友评论

        本文标题:BZOJ-1014: [JSOI2008]火星人prefix(字

        本文链接:https://www.haomeiwen.com/subject/cfrkzftx.html