BZOJ-3277: 串（ST算法+二分+后缀数组）

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

首先将所有字符串串在一次做SA，然后我们对于sa上，枚举每个串的每个后缀，求出有几个该后缀的前缀符合条件，那么就要判定区间里面有多少个不同的数，所幸的是这里只需要求是否该数目>=k，所以对于每个位置记录个L（x），表示[L(x),x]中刚好有k个不同的数，且L（x）最大（参考了CF官方题解），然后CF上的题解是对于每个后缀二分出长度，然后是O（n log^2 n的算法），但是O（n log^2 n）在本题仍然会TLE，那么我们发现枚举后缀的时候，如果后缀c+S有n个前缀合法（c表示一个字符，s表示一个串），那么对于后缀S，至少有n-1个前缀合法（如果c+S有n个前缀出现不小于k次，那么其子串也是），那么我们就用类似求SA里的height一样的方法，记录一下前面的后缀的合法前缀数，然后这样的总复杂度就成了均摊O（n log n），可以AC。

代码：

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

 

using namespace std ;

 

#define rep( i , x ) for ( int i = 0 ; i ++ < x ; )

#define DOWN( i , r , l ) for ( int i = r ; i >= l ; -- i )

#define REP( i , l , r ) for ( int i = l ; i <= r ; ++ i )

 

const int maxn = 201000 , inf = 0x7ffffff ;

 

int n , k , num[ maxn ] , Beg[ maxn ] , End[ maxn ] , pos = 0 ;

char str[ maxn ] , s[ maxn ] ;

 

int sa[ maxn ] , Rank[ maxn ] , w[ maxn ] , x[ maxn ] , y[ maxn ] , r[ maxn ] , height[ maxn ] ;

 

inline void build_sa(  ) {

    int N , b = 1 , M = 0 , len = pos ;

    rep( i , pos ) M = max( M , Rank[ i ] = s[ i ] ) ;

    x[ 0 ] = y[ 0 ] = 0 ;

    do {

        rep( i , pos ) {

            x[ i ] = Rank[ i ] , y[ i ] = i + b <= pos ? Rank[ i + b ] : 0 ;

        }

        b <<= 1 ;

        REP( i , 0 , M ) w[ i ] = 0 ;

        rep( i , pos ) ++ w[ y[ i ] ] ;

        rep( i , M ) w[ i ] += w[ i - 1 ] ;

        rep( i , pos ) r[ w[ y[ i ] ] -- ] = i ;

        REP( i , 0 , M ) w[ i ] = 0 ;

        rep( i , pos ) ++ w[ x[ r[ i ] ] ] ;

        rep( i , M ) w[ i ] += w[ i - 1 ] ;

        DOWN( i , pos , 1 ) sa[ w[ x[ r[ i ] ] ] -- ] = r[ i ] ;

        N = 0 ;

        rep( i , pos ) {

            if ( i == 1 || x[ sa[ i ] ] != x[ sa[ i - 1 ] ] || y[ sa[ i ] ] != y[ sa[ i - 1 ] ] ) ++ N ;

            Rank[ sa[ i ] ] = N ;

        }

        M = N ;

    } while ( N < pos ) ;

    int rec = 0 ;

    rep( i , pos ) {

        for ( ; i + rec <= pos && sa[ Rank[ i ] - 1 ] + rec <= pos && s[ i + rec ] == s[ sa[ Rank[ i ] - 1 ] + rec ] ; ++ rec ) ;

        height[ Rank[ i ] ] = rec ;

        rec = max( rec - 1 , 0 ) ;

    }

}

 

int st[ maxn << 1 ][ 21 ] , B = 0 ;

 

inline void Init_rmq(  ) {

    for ( ; ( 1 << B ) < pos ; B ++ ) ;

    rep( i , pos ) st[ i ][ 0 ] = height[ i ] ;

    rep( i , B ) rep( j , pos ) {

        st[ j ][ i ] = min( st[ j ][ i - 1 ] , st[ j + ( 1 << ( i - 1 ) ) ][ i - 1 ] ) ;

    }

}

 

inline int query( int l , int r ) {

    if ( l > r ) return inf ;

    int k = int( log2( r - l + 1 ) ) ;

    return min( st[ l ][ k ] , st[ r - ( 1 << k ) + 1 ][ k ] ) ;

}

 

int left[ maxn ] , cnt[ maxn ] , kind = 0 ;

 

typedef long long ll ;

ll ans = 0 ;

 

inline bool check( int p , int x ) {

    int first , last , L , R , mid ;

    if ( height[ p ] < x ) first = p ; else {

        L = 1 , R = p ;

        while ( R - L > 1 ) {

            mid = ( L + R ) >> 1 ;

            if ( query( mid , p ) >= x ) R = mid ; else L = mid ;

        }

        first = R - 1 ;

    }

    if ( height[ p + 1 ] < x ) last = p ; else {

        L = p + 1 , R = pos + 1 ;

        while ( R - L > 1 ) {

            mid = ( L + R ) >> 1 ;

            if ( query( p + 1 , mid ) >= x ) L = mid ; else R = mid ;

        }

        last = L ;

    }

    return left[ last ] >= first ;

}

 

int last ;

 

int main(  ) {

    scanf( "%d%d" , &n , &k ) ;

    rep( i , n ) {

        scanf( "%s" , str ) ;

        int len = strlen( str ) ;

        Beg[ i ] = pos + 1 , End[ i ] = pos + len ;

        REP( j , 0 , ( len - 1 ) ) {

            s[ ++ pos ] = str[ j ] ; num[ pos ] = i ;

        }

        s[ ++ pos ] = '&' ;

    }

    build_sa(  ) ;

    Init_rmq(  ) ;

    memset( cnt , 0 , sizeof( cnt ) ) ;

    int rec = 1 ;

    rep( i , pos ) {

        if ( ! ( cnt[ num[ sa[ i ] ] ] ++ ) ) ++ kind ;

        if ( kind >= k ) {

            for ( ; kind - ( cnt[ num[ sa[ rec ] ] ] == 1 ) >= k ; kind -= ( cnt[ num[ sa[ rec ] ] ] == 1 ) , -- cnt[ num[ sa[ rec ++ ] ] ] ) ;

            left[ i ] = rec ;

        } else left[ i ] = 0 ;

    }

    rep( i , n ) {

        ans = last = 0 ;

        REP( j , Beg[ i ] , End[ i ] ) {

            for ( ; check( Rank[ j ] , last + 1 ) && last <= End[ i ] - j ; ++ last ) ;

            ans += ll( last ) ;

            last = max( last - 1 , 0 ) ;

        }

        printf( "%lld " , ans ) ;

    }

    printf( "\n" ) ;

    return 0 ;

}