题面：
题目描述
很久很久以前，森林里住着一群跳蚤。一天，跳蚤国王得到了一个神秘的字符串，它想进行研究。首先，他会把串分成不超过 k 个子串，然后对于每个子串 S，他会从S的所有子串中选择字典序最大的那一个，并在选出来的 k 个子串中选择字典序最大的那一个。他称其为“魔力串”。现在他想找一个最优的分法让“魔力串”字典序最小。
输入格式
第一行一个整数 k，k≤15
接下来一个长度不超过 10^5的字符串 s。
输出格式
输出一行，表示字典序最小的“魔力串”。
样例
输入样例
2
ababa
输出样例
ba
样例解释
分成aba和ba两个串，其中字典序最大的子串为ba
看到让最大的最小我们就想到二分答案，二分答案在原字符串的所有不同子串中的排名。知道了排名，我们用后缀数组就很好求出答案串是什么(记录其在原串中的起始位置和结束位置)，具体方法见代码。
这里还有一点要考虑的是二分的上界也就是子串的个数。其实这很好求就是∑n-sa[i]+1-height[i[。毕竟所有的子串都是一个后缀的前缀，对于一个后缀sa[i]，他有n-sa[i]+1个前缀，但是有height[i]个前缀与前面的重复，已经算过了，就得减掉。
然后我们来考虑如何判定。这里我默认大家都会求LCP(LCP(i, j)=min{height[k]}(rank[i]<k<=rank[j])，然后用ST表nlogn预处理，O(1)时间内求出LCP)。记录一个cut=i代表你上次在i-1和i之间切了一刀，令cut的初值为n+1。再记录一个cnt代表切了多少次，如果cnt>=k则不成立(这里注意切了cnt到右cnt+1个块，所以是>=)。每次判定先求出当且串的起始和结束位置记为L, R，然后再从后往前枚举后缀i，求出i和L的LCP。若LCP==0，则判断s[L]和s[i]的大小关系，若s[i]>s[L]则返回false(根据题目要求s[L…R]应是一个快内最大的)。求min{LCP, cut - i, R - L + 1}。若cut-i最小，则说明上次剪的地方到现在这一段都是相同的(<LCP)或者比当前串还短(<R-L+1)，此时这个位置一定不需要剪，直接continue。若R-L+1最小或者LCP最小且s[L+LCP]<s[i+LCP]时我们就需要分块。令cut = i + 1，cnt++，然后再判断cnt与k的关系即可。
上代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = ;
ll k;
ll n, m;
ll sa[N], rnk[N], v1[N], v2[N], sum[N], height[N];
ll st[N][];
char s[N];
bool cmp(ll *t, ll a, ll b, ll l) {
return t[a] == t[b] && t[a + l] == t[b + l];
}
void da() {
ll i, j, p = ;
for (i = ; i <= m; i++) sum[i] = ;
for (i = ; i <= n; i++) sum[rnk[i] = s[i]]++;
for (i = ; i <= m; i++) sum[i] += sum[i - ];
for (i = n; i >= ; i--) sa[sum[rnk[i]]--] = i;
for (j = ; j <= n; j *= , m = p) {
for (p = , i = n - j + ; i <= n; i++) v2[++p] = i;
for (i = ; i <= n; i++) if (sa[i] > j) v2[++p] = sa[i] - j;
for (i = ; i <= n; i++) v1[i] = rnk[v2[i]];
for (i = ; i <= m; i++) sum[i] = ;
for (i = ; i <= n; i++) sum[v1[i]]++;
for (i = ; i <= m; i++) sum[i] += sum[i - ];
for (i = n; i >= ; i--) sa[sum[v1[i]]--] = v2[i];
for (swap(rnk, v2), rnk[sa[]] = , p = , i = ; i <= n; i++) {
rnk[sa[i]] = cmp(v2, sa[i - ], sa[i], j) ? p - : p++;
}
}
}
void calheight() {
ll i, j, p = ;
for (i = ; i <= n; i++) {
if (p) p--;
j = sa[rnk[i] - ];
while (s[i + p] == s[j + p]) p++;
height[rnk[i]] = p;
}
}
void st_pre() {
for (ll i = ; i <= n; i++) st[i][] = height[i];
for (ll j = ; j <= ; j++) {
for (ll i = ; i <= n; i++) {
if (i + ( << (j - )) > n) break;
st[i][j] = min(st[i][j - ], st[i + ( << (j - ))][j - ]);
}
}
}
ll LCP(ll l, ll r) {
if (l == r) return n - sa[l] + ;
if (l > r) swap(l, r);
l++;
ll kk = log(r - l + ) / log();
return min(st[l][kk], st[r - ( << kk) + ][kk]);
}
ll pos_l, pos_r, ans_l, ans_r;
void get_string(ll mid) {
for (ll i = ; i <= n; i++) {
ll tmp = n - sa[i] - height[i] + ;
if (mid > tmp) {
mid -= tmp;
} else {
pos_l = sa[i];
pos_r = sa[i] + height[i] - + mid;
return;
}
}
}
bool check() {
for (ll i = n, cut = n + , cnt = ; i >= ; i--) {
ll lcp = LCP(rnk[pos_l], rnk[i]);
if (lcp == && s[i] > s[pos_l]) return false;
lcp = min(lcp, min(pos_r - pos_l + , cut - i));
if (lcp == cut - i) continue;
if (lcp == pos_r - pos_l + || s[i + lcp] > s[pos_l + lcp]) {
cnt++;
cut = i + ;
if (cnt > k) return false;
}
} return true;
}
int main() {
scanf("%lld%s", &k, s + );
k--;
n = strlen(s + );
m = ;
da();
calheight();
st_pre();
ll l = , r = ;
for (ll i = ; i <= n; i++) {
r += n - sa[i] - height[i] + ;
}
while (l <= r) {
ll mid = (l + r) >> ;
get_string(mid);
if (check()) {
ans_l = pos_l;
ans_r = pos_r;
r = mid - ;
} else {
l = mid + ;
}
}
for (ll i = ans_l; i <= ans_r; i++) {
cout << s[i];
}
return ;
}