题目概述

有一个串 $S$ ，现在要把 $S$ 分成不超过 $k$ 段，从每一个子串选出最大的子串，再从这些最大的子串中选出最大的串"JZ串"，求最小的"JZ串"（题面有误，应该是最小的而不是最大的）。

解题报告

最大值最小想到二分，但是这怎么二分答案？直接二分串肯定是不行的，所以我们可以二分 $k$ 表示第 $k$ 大的串，至于怎么求第 $k$ 大的串，后缀数组就可以解决。

然后我们考虑验证，在原串上跑，如果目前区间中有子串大于子串 $k$（用LCP判断即可），就说明需要换组。如果组的数量不超过 $K$ 就验证成功。

如果正着来，每次添加了一个字符实际上添加了一堆子串，肯定会TLE。

所以我们反着来，会发现每次添加了一个字符产生的子串中只有最长的那个有用（显然），这样效率就正常了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,Log=17;

int K,n,l,r,SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5];
int RMQ[maxn+5][Log+5],lg2[maxn+5];char s[maxn+5];

inline void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i];
}
inline void Make(int n){
    int m=256;for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i;Sort(n,m);
    for (int k=1,p=0;p<n;m=p,k<<1){
        p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k;
        Sort(n,m);memcpy(t,rk,sizeof(rk));rk[SA[1]]=p=1;
        for (int i=2;i<=n;rk[SA[i++]]=p) p+=t[SA[i-1]]!=t[SA[i]]||t[SA[i-1]+k]!=t[SA[i]+k];
    }
    for (int i=1,k=0;i<=n;RMQ[rk[i++]][0]=k) {if (k) k--;while (s[i+k]==s[SA[rk[i]-1]+k]) k++;}
    for (int j=1;j<=Log;j++) for (int i=2;i+(1<<j)-1<=n;i++) RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
    for (int i=2;i<=n;i++) lg2[i]=lg2[i>>1]+1;
}
inline void getsub(LL mid){
    for (int i=1;i<=n;i++){
        mid-=n-SA[i]+1-RMQ[i][0];
        if (mid<=0) {l=SA[i];r=n+mid;return;}
    }
}
inline int LCP(int x,int y){
    if (x==y) return n-x+1;x=rk[x];y=rk[y];
    if (x>y) swap(x,y);x++;int k=lg2[y-x+1];
    return min(RMQ[x][k],RMQ[y-(1<<k)+1][k]);
}
inline bool cmp(int L,int R,int l,int r){
    int lcp=LCP(L,l),A=R-L+1,B=r-l+1;
    if (lcp>A) lcp=A;if (lcp>B) lcp=B;
    if (lcp==A||lcp==B) return A>B;
    return s[L+lcp]>s[l+lcp];
}
inline bool check(LL mid){
    getsub(mid);for (int i=1;i<=n;i++) if (s[i]>s[l]) return false;
    int k=1,lst=n;for (int i=n-1;i;i--) if (cmp(i,lst,l,r)) k++,lst=i;
    return k<=K;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&K);scanf("%s",s+1);Make(n=strlen(s+1));RMQ[1][0]=0;
    LL L=1,R=0;for (int i=1;i<=n;i++) R+=n-SA[i]+1-RMQ[i][0];
    for (LL mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) check(mid)?R=mid-1:L=mid+1;
    getsub(L);for (int i=l;i<=r;i++) putchar(s[i]);return 0;
}