BZOJ 4310 跳蚤 题解

Statement

把 \(S\) 分成不超过 \(k\) 段，使每段的最大子串中的最大串最小。输出这个串。

Solution

按排名二分这个串，check 中从右往左贪心地划分，需要实现 \(O(1)\) 比较两个子串大小。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define reo(i, j, k) for (int i = (j); i >= (k); --i)
typedef long long ll;
const int N = 2e5 + 10, LN = 20;
int n, k;
string s;

int m = 131, p, sa[N], rk[N], se[N], cnt[N], height[N];
void Rsort() {
	rep(i, 1, m) cnt[i] = 0;
	rep(i, 1, n) ++cnt[rk[i]];
	rep(i, 1, m) cnt[i] += cnt[i - 1];
	reo(i, n, 1) sa[cnt[rk[se[i]]]--] = se[i];
}
void SA() {
	if (n == 1) return (void)(sa[1] = rk[1] = 1);
	rep(i, 1, n) rk[i] = s[i - 1], se[i] = i;
	Rsort();
	for (int w = 1; w < n; w <<= 1, m = p) {
		p = 0;
		rep(i, n - w + 1, n) se[++p] = i;
		rep(i, 1, n) if (sa[i] > w) se[++p] = sa[i] - w;
		Rsort(), swap(rk, se), p = 0;
		rep(i, 1, n)
			if (se[sa[i]] == se[sa[i - 1]] && se[sa[i] + w] == se[sa[i - 1] + w]) rk[sa[i]] = p;
			else rk[sa[i]] = ++p;
		if (p == n) break;
	}
}
void Getheight() {
	int h = 0;
	rep(i, 1, n) {
		if (h) --h;
		while (s[i + h - 1] == s[sa[rk[i] - 1] + h - 1]) ++h;
		height[rk[i]] = h;
	}
}
int ln, Mn[N][LN];
void initST() {
	ln = __lg(n);
	rep(i, 1, n) Mn[i][0] = height[i];
	rep(j, 1, ln)
		rep(i, 1, n - (1 << j) + 1) Mn[i][j] = min(Mn[i][j - 1], Mn[i + (1 << (j - 1))][j - 1]);
}
int AskMn(int l, int r) {
	int g = __lg(r - l + 1);
	return min(Mn[l][g], Mn[r - (1 << g) + 1][g]);
}
int LCP(int x, int y) {
	if (x == y) return n - x + 1;
	int l = rk[x], r = rk[y];
	if (l > r) swap(l, r);
	++l;
	return AskMn(l, r);
}
int Compare(int l1, int r1, int l2, int r2) { // -1: <, 0: =, 1: >
	int len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
	int lcp = min({len1, len2, LCP(l1, l2)});
	if (lcp < len1 && lcp < len2) {
		if (s[l1 + lcp - 1] < s[l2 + lcp - 1]) return -1;
		if (s[l1 + lcp - 1] == s[l2 + lcp - 1]) return 0;
		if (s[l1 + lcp - 1] > s[l2 + lcp - 1]) return 1;
	} else {
		if (len1 == len2) return 0;
		if (len1 < len2) return -1;
		if (len1 > len2) return 1;
	}
	assert(0);
}
void init() {
	SA(), Getheight(), initST();
}

pair<int, int> GetLR(ll x) {
	rep(i, 1, n) {
		ll now = n - sa[i] + 1 - height[i];
		if (x > now) {
			x -= now;
		} else {
			int l = sa[i], len = height[i] + x;
			return make_pair(l, l + len - 1);
		}
	}
	assert(0);
}

string GetString(ll x) {
	string res;
	pair<int, int> LR = GetLR(x);
	rep(i, LR.first, LR.second) res += s[i - 1];
	return res;
}

int check(ll x) {
	pair<int, int> LR = GetLR(x);
	int L = LR.first, R = LR.second;
	int r = n, ans = 1;
	reo(l, n, 1) 
		if (Compare(l, r, L, R) == 1) ++ans, r = l;
	return ans <= k;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> k >> s, n = s.length();
	init();
	ll sum = 0;
	rep(i, 1, n) sum += n - sa[i] + 1 - height[i];
	ll l = 1, r = sum, mid = 0, res = sum;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (check(mid)) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	cout << GetString(res) << '\n';
	return 0;
}