Description
很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。
首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。
现在他想找一个最优的分法让“魔力串”字典序最小。
Input
第一行一个整数 k。
接下来一个长度不超过 105 的字符串 S。
Output
输出一行，表示字典序最小的“魔力串”。
Sample Input
13
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba
bcbcbacbbbbbabbacbcbacbbababaabbbaabacacbbbccaccbcaabcacbacbcabaacbccbbcbcbacccbcccbbcaacabacaaaaaba
Sample Output
cbc
HINT
S的长度<=100000
这应该是目前见过的最鬼的一道后缀数组题了。。。
最大值最小，考虑二分答案。一开始把子串的排名和第k小的子串求出来了，但是并不知道如何check；
最初的想法是从rnk[1]开始，当前的后缀如果有本质不同的子串排名>mid，就从那个>mid的点为后缀的开头重分一组。
但这样萎得稀巴烂，因为首先这样并不能保证这些子串的子串的排名<=mid，而且这样的贪心也没有正确性。
考虑从sa数组从后往前贪心，每次往前移的时候要把a[i..last]和排名为mid的子串比较一下字典序，如果大于就重分一组，比较子串的话字典序可以找这两个子串的lcp来实现；
这样为什么就保证了子串的子串的排名<=mid呢？因为以i开头的后缀，长度越长字典序越大，所以a[i..last]是以i开头的子串的字典序最大值，最大值都<=mid，其余的子串肯定也都满足。。。
用lst大佬的话来说就是一段区间中，字典序最大的子串的结尾一定是区间的末尾(和我一个意思。。。)，所以可以从后往前贪心。。。
(i为当前扩展的节点，last为这个子串的最后一个元素)
最后判断分的组数是否超过k;
至于本质不同的子串的排名是经典板子，不做赘述，每次打一个新的后缀数组题就感觉以前打的一些东西是错的。。。
是不是求LCP的时候要特判(l==r) ???
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define RG register
#define ll long long
using namespace std;
const int N=1e6+10;
struct data{
int fir,sec,id;
}x[N];
int sa[N],y[N],rnk[N],rk,height[N],len,k,lx,rx,pre[N],pre2[N],ST[N][20];
ll sum[N];
char a[N];
bool cmp(const data &a,const data &b){
if(a.fir==b.fir) return a.sec<b.sec;
else return a.fir<b.fir;
}
void work2(){
rk=1;y[x[1].id]=rk;
for(RG int i=2;i<=len;i++){
if(x[i-1].fir!=x[i].fir||x[i-1].sec!=x[i].sec) rk++;
y[x[i].id]=rk;
}
}
void work(){
sort(x+1,x+1+len,cmp);work2();
for(RG int i=1;i<=len;i<<=1){
for(RG int j=1;j+i<=len;j++) x[j].fir=y[j],x[j].sec=y[j+i],x[j].id=j;
for(RG int j=len-i+1;j<=len;j++) x[j].fir=y[j],x[j].sec=0,x[j].id=j;
sort(x+1,x+1+len,cmp);work2();
if(rk==len) break;
}
for(int i=1;i<=len;i++) sa[y[i]]=i;
}
void get_height(){
int kk=0;for(RG int i=1;i<=len;i++) rnk[sa[i]]=i;
for(RG int i=1;i<=len;i++){
if(kk) kk--;
int j=sa[rnk[i]-1];
while(a[i+kk]==a[j+kk]) kk++;
height[rnk[i]]=kk;
}
}
void make_ST(){
pre[0]=1;for(int i=1;i<=16;i++) pre[i]=pre[i-1]<<1;
pre2[0]=-1;for(int i=1;i<=len;i++) pre2[i]=pre2[i>>1]+1;
for(RG int i=2;i<=len;i++) ST[i][0]=height[i];
for(RG int j=1;j<=16;j++)
for(RG int i=2;i<=len;i++){
if(i+pre[j]-1<=len){
ST[i][j]=min(ST[i][j-1],ST[i+pre[j-1]][j-1]);
}
}
}
int query(int l,int r){
if(l>r) swap(l,r);
int x=pre2[r-l+1];
return min(ST[l][x],ST[r-pre[x]+1][x]);
}
int LCP(int l,int r){
if(l==r) return len-sa[l];
if(l>r) swap(l,r);
return query(l+1,r);
}
bool compare(int l1,int r1,int l2,int r2){
int len1=r1-l1+1,len2=r2-l2+1,lcp=LCP(rnk[l1],rnk[l2]);
lcp=min(lcp,min(len1,len2));
if(lcp!=len1&&lcp!=len2) return a[l1+lcp]<=a[l2+lcp];
if(lcp==len1) return 1;
if(lcp==len2) return 0;
}
void get_kth(ll kk){
for(RG int i=1;i<=len;i++){
if(sum[i]>=kk){
lx=sa[i];rx=sa[i]+height[i]-1+(kk-sum[i-1]);
break;
}
}
}
bool check(ll mid){
get_kth(mid);int last=len,ret=1;
for(RG int i=len;i>=1;i--){
if(!compare(i,last,lx,rx)){ret++,last=i;}
if(ret>k) return 0;
}
return 1;
}
int main(){
cin>>k;scanf("%s",a+1);len=strlen(a+1);
for(RG int i=1;i<=len;i++) x[i].id=i,x[i].fir=x[i].sec=a[i]-'a'+1;
work();get_height();
for(int i=1;i<=len;i++){sum[i]=sum[i-1]+len-sa[i]+1-height[i];}
ll L=1,R=sum[len],ans;make_ST();
while(L<=R){
ll mid=(L+R)>>1;
if(check(mid)) ans=mid,R=mid-1;
else L=mid+1;
}
get_kth(ans);
for(int i=lx;i<=rx;i++) cout<<a[i];
}