BZOJ 4310 跳蚤

不太会做，看了题解才会的。

首先要二分子串。后缀排序后，本质不同子串个数其实就是 $ \sum_i n + 1 - sa[i] - height[i] $ ，考虑排序后的后缀，本质不同的子串个数其实就是本质不同这些后缀的前缀个数。一个后缀的贡献就是这个后缀的所有前缀，减去自己和上一个后缀的 LCP 。（感性理解一下吧QAQ）

其实二分后，这个子串是可以确定的。枚举一下后缀排序后的后缀就可以得到。

假设我们当前二分到的子串是 $ s[L,R] $ ，怎么确定是否可以分成很多份，使得每一份里最大的子串也不大于这个？

这个时候就要贪心了，从后往前划分，如果往开头添加当前这个字符，整个串都没有大于 $ s[L,R] $ 我们就添加它，否则在这里 cut 开。

这个贪心很容易证成立的，显然可以添加这个字符的话我们会尽力去添加它，因为一定不会让情况变得不优秀。

然后这个比较大小还有点毒瘤，如果要比较 $ s[l,r] $ 和 $ s[L,R] $ 大小，先拿 $ l,n $ 和 $ L , n $ 比较，这个可以 $ O(1) $

• 假设左端点后缀大小较大的是 $ l,r $ 长度为 $ l_1 $ ，大小较小的是 $ L,R $ 长度是 $ l_2 $

• 考虑什么情况最终大小关系不是后缀大小关系呢？

  • 当 $ l_1 < l_2 $ ，如果同时这两个后缀的 $ LCP $ 长度大于了 $ l_1 $ ，这就意味着原来的大小关系需要反过来。否则大小关系和原来一致。
  • 如果 $ l_1=l_2 $ 这种情况只有 $ LCP $ 长度大于了 $ l_1 $ 才有他们相等，否则大小关系与原来一致。
  • 如果 $ l_1 > l_2 $ ，大小关系和原来一致。

  画下图就很容易想到了！

看起来不是很好写呢~ awa

而且不太明白为啥 $ k $ 很小。

记得longlong啊。。没longlong挂了两发。。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 100006
#define C 130
int k;
char ch[MAXN];
int sa[MAXN] , tp[MAXN] , rnk[MAXN] , buc[MAXN] , len , ht[MAXN];
int P[MAXN][19];
void init(  ) {
    len = strlen( ch + 1 ); int m = C;
    for( int i = 1 ; i <= len ; ++ i ) ++ buc[rnk[i] = ch[i]];
    for( int i = 1 ; i <= m ; ++ i ) buc[i] += buc[i-1];
    for( int i = len ; i >= 1 ; -- i ) sa[buc[rnk[i]] --] = i;
    for( int k = 1 , p = 0 ; p < len ; k <<= 1 ) {
        p = 0;
        for( int i = 0 ; i <= m ; ++ i ) buc[i] = 0;
        for( int i = len - k + 1 ; i <= len ; ++ i ) tp[++p] = i;
        for( int i = 1 ; i <= len ; ++ i ) if( sa[i] > k ) tp[++p] = sa[i] - k;
        for( int i = 1 ; i <= len ; ++ i ) ++ buc[rnk[i]];
        for( int i = 1 ; i <= m ; ++ i ) buc[i] += buc[ i-1 ];
        for( int i = len ; i >= 1 ; -- i ) sa[buc[rnk[tp[i]]] --] = tp[i];
        p = 1;
        swap( rnk , tp );
        rnk[sa[1]] = 1;
        for( int i = 2 ; i <= len ; ++ i )
            rnk[sa[i]] = ( tp[sa[i]] == tp[sa[i-1]] && tp[sa[i] + k] == tp[sa[i-1] + k] ) ? p : ++ p;
        m = p;
    }
    for( int i = 1 ; i <= len ; ++ i ) rnk[sa[i]] = i;
    for( int i = 1 , k = 0 ; i <= len ; ++ i ) {
        if( k ) -- k;
        while( ch[i + k] == ch[sa[rnk[i] - 1] + k] ) ++ k;
        ht[rnk[i]] = k; P[rnk[i]][0] = k;
    }
}

void initst( ){
    for( int k = 1 ; k < 19 ; ++ k )
        for( int i = 1 ; i <= len - ( 1 << k ) + 1 ; ++ i )
            P[i][k] = min( P[i][k - 1] , P[i + ( 1 << k - 1 )][k - 1] );
}
int que( int l , int r ) {
    if( l > r ) swap( l , r ); else if( l == r ) return 0x3f3f3f3f;
    ++ l;
    int L = 31 - __builtin_clz( r - l + 1 );
    return min( P[l][L] , P[r - ( 1 << L ) + 1][L] );
}

int L , R;
void getlr( long long x ) {
    for( int i = 1 ; i <= len ; ++ i ) {
        int k = len + 1 - ht[i] - sa[i];
        if( x > k ) x -= k;
        else { L = sa[i]; R = sa[i] + ht[i] + x - 1; break; }
    }
}
bool cmp( int l , int r , int L , int R ) { // return S[l,r] > S[L,R]
    int ret = 1;
    if( rnk[l] < rnk[L] ) swap( l , L ) , swap( r , R ) , ret ^= 1;
    int l1 = r - l + 1 , l2 = R - L + 1;
    if( l1 < l2 ) {
        int lp = que( rnk[l] , rnk[L] );
        if( lp >= l1 ) return ret ^ 1;
        else return ret;
    } else if( l1 == l2 ) {
        int lp = que( rnk[l] , rnk[L] );
        if( lp >= l1 ) return 0;
        else return ret;
    }
    return ret;
}
bool chk( long long x ) {
    getlr( x );
    int r = len , t = 0;
    for( int i = len ; i >= 1 ; -- i ) {
        if( ch[i] > ch[L] ) return false;
        if( cmp( i , r , L , R ) ) r = i , ++ t;
        if( t >= k ) return false;
    }
    return true;
}

int main() {
//    freopen("2.in","r",stdin);
//    freopen("ot","w",stdout);
    cin >> k;
    scanf("%s",ch+1);
    init();
    initst();
    long long tot = 0;
    for( int i = 1 ; i <= len ; ++ i ) tot += len + 1 - ht[i] - sa[i];
    long long l = 1 , r = tot;
    while( l <= r ) {
        long long m = l + r >> 1;
        if( chk ( m ) ) r = m - 1;
        else l = m + 1;
//        cout << m << endl;
    }
    getlr( l );
    for( int i = L ; i <= R ; ++ i ) putchar( ch[i] );
}