P5108 仰望半月的夜空-526互联

Day \(\mathbb P_1^2 + \mathbb P_2^2 + \mathbb P_3^2\)。

不考虑左端点最小，如何求出一个字典序最小子串，只需要建出后缀数组后找最小的 \(i\) 满足 \(n-\text{sa}_i+1\ge L\)，然后取 \(S[\text{sa}_i,\text{sa}_i+L-1]\) 即可。

现在的问题在于可能存在一个 \(j>i\) 使得 \(S[\text{sa}_i,\text{sa}_i+L-1]=S[\text{sa}_j,\text{sa}_j+L-1]\)，并且 \(\text{sa}_i>\text{sa}_j\)，这样的话 \(S[\text{sa}_j,\text{sa}_j+L-1]\) 的左端点就更小了。

但是注意到 \(\text{sa}\) 是按照字典序排序的，也就是说，\(\text{lcp}(S[\text{sa}_i,n],S[\text{sa}_j,n])\) 在 \(i\) 固定时随着的 \(j\) 递增而单调不升，那么合法的 \(j\) 是一段以 \(i\) 为左端点的区间 \([i,p]\)。如果我们求出了这个区间，我们就查询 \(k\in[i,p]\) 的 \(\text{sa}_k\) 的最小值即可。

由于两个后缀 \(S[\text{sa}_i,n],S[\text{sa}_j,n]\) 的 LCP 长度相当于 \(\min\limits_{k\in [i+1,j]}\text{height}_k\)，所以处理出 \(\text{height}\) 数组后建 ST 表支持 \(O(1)\) RMQ，然后直接二分右端点 \(p\) 找到最小的 \(p\) 满足 \(\text{lcp}(S[\text{sa}_i,n],S[\text{sa}_j,n])\ge L\) 就做完了。

复杂度 \(O(n\log n)\)。

// Problem: P5108 仰望半月的夜空
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5108
// Memory Limit: 500 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef tuple<int, int, int> tu;
bool Mbe;

const int M = 25;
const int N = 3e5 + 200;

int n, m, len, t[N], s[N];
int sa[N], rk[N], id[N], ct[N], h[N];

void rst() {
	memset(ct, 0, sizeof(int) * (m + 5));
	for (int i = 1; i <= n; i++) ct[rk[i]]++;
	for (int i = 1; i <= m; i++) ct[i] += ct[i - 1];
	for (int i = n; i; i--) sa[ct[rk[id[i]]]--] = id[i];
}

void SA() {
	rst();
	for (int w = 1, p = 0; w <= n && p != n; w <<= 1, m = p) {
		p = 0;
		for (int i = n - w + 1; i <= n; i++) id[++p] = i;
		for (int i = 1; i <= n; i++) if (sa[i] > w) id[++p] = sa[i] - w;
		rst(), swap(rk, id), p = rk[sa[1]] = 1;
		for (int i = 2; i <= n; i++) rk[sa[i]] = (id[sa[i]] == id[sa[i - 1]] && id[sa[i] + w] == id[sa[i - 1] + w]) ? p : ++p;
	}
	for (int i = 1, j = 0; i <= n; i++) {
		if (j) j--;
		while (s[i + j] == s[sa[rk[i] - 1] + j]) j++;
		h[rk[i]] = j;
	}
}

struct ST {
	int f[N][M];
	void init(int *s) { 
		for (int i = 1; i <= n; i++) f[i][0] = s[i]; 
		for (int j = 1; (1 << j) <= n; j++)
			for (int i = 1; i + (1 << j) - 1 <= n; i++)
				f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
	}
	int qry(int l, int r) {
		int len = __lg(r - l + 1);
		return min(f[l][len], f[r - (1 << len) + 1][len]);
	}
} S, T;

void solve() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		if (m == 26) {
			char ch; cin >> ch;
			s[i] = ch - 'a' + 1;
		} else cin >> s[i];
		t[++len] = s[i], id[i] = i;
	}
	sort(t + 1, t + len + 1), len = unique(t + 1, t + len + 1) - t - 1;
	for (int i = 1; i <= n; i++) rk[i] = s[i] = lower_bound(t + 1, t + len + 1, s[i]) - t;
	m = len + 1, SA(), S.init(h), T.init(sa);
	for (int p = 1, i = 1; p <= n; p++) {
		while (sa[i] > n - p + 1) i++;
		int pos = i;
		for (int l = i + 1, r = n; l <= r; ) {
			int md = (l + r) >> 1;
			if (S.qry(i + 1, md) >= p) pos = md, l = md + 1;
			else r = md - 1;
		}
		cout << T.qry(i, pos) << ' ';
	}
}

bool Med;
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
	#ifdef FILE
		freopen("1.in", "r", stdin);
		freopen("1.out", "w", stdout);
	#endif
	int T = 1;
	// cin >> T;
	while (T--) solve();
	cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
	return 0;
}