仰望半月的夜空 题解
可以的话，支持一下原作吧...
这道题数据很弱.....
因此各种乱搞估计都是能过的....
算法一
暴力长度然后判断判断，复杂度\(O(n^3)\)
期望得分15分
算法二
通过二分+\(hash\)或者等等来优化字典序比较，复杂度\(O(n^2 \log n)\)，可能要松一下
期望得分30分
ps:好吧有55分...
算法三
我们考虑字符集非常小的情况
我们猜想出题人很难卡掉玄学做法，因此我们就想一个玄学做法
我们考虑用\(SAM\)来处理这个问题
建出\(SAM\)后，我们用\(dp\)预处理出一个点向后走最长能走多远
然后在\(SAM\)上根据字典序找到每个长度分别对应哪个集合
取对应集合的\(right\)集合中的最小值即可
复杂度是个玄学，但是能通过字符集很小和数据随机的点
期望得分55~75分
不会在字符集很小的情况下造数据，求大佬
算法四
注意到实际上复杂度很高是因为我们在一个\(DAG\)上寻找答案
实际上我们建出后缀树，然后在树上寻找对应集合即可
复杂度可以做到\(O(n \log n)\)
字符集较小的时候可以直接\(O(n)\)
期望得分100分
算法五
考虑用\(SA\)来解决这个问题
不难发现，给后缀排好序之后，按照长度维护一个单调栈
不妨设单调栈中的后缀分别为\(i_1, i_2, ..., i_p\)
那么，长度\(L(i_1) + 1 \sim L(i_2)\)对应的字典序最小的串一定是以\(i_2\)为开头的
这样，我们就可以找到这\(n\)个串
然后再用二分找到这个串在后缀数组中对应的区间，用线段树或者\(st\)表(暴力也能过)来维护\(sa\)的最小值即可
复杂度\(O(n \log n)\)
期望得分100分
几乎是个模板字符串吧.....
Q：前半段和后半段相等的串有啥用啊？
A：我也不知道，所以才放在那里的....
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define ri register int
#define rep(io, st, ed) for(ri io = st; io <= ed; io ++)
#define drep(io, ed, st) for(ri io = ed; io >= st; io --)
#define gc getchar
inline int read() {
int p = 0, w = 1; char c = gc();
while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
return p * w;
}
const int sid = 500050;
const int ssd = 2000050;
char t[sid];
int n, S, top, s[sid], T[sid];
int nc[sid], p1[sid], p2[sid], ip[sid];
int sa[sid], rk[sid], lg[sid], bit[sid], st[sid][20];
void init() {
rep(i, 0, 25) bit[i] = 1 << i;
rep(i, 2, 400000) lg[i] = lg[i >> 1] + 1;
}
void rsort(int n, int m) {
rep(i, 1, n) nc[p2[i]] ++;
rep(i, 1, m) nc[i] += nc[i - 1];
rep(i, 1, n) ip[nc[p2[i]] --] = i;
rep(i, 0, m) nc[i] = 0;
rep(i, 1, n) nc[p1[i]] ++;
rep(i, 1, m) nc[i] += nc[i - 1];
drep(i, n, 1) sa[nc[p1[ip[i]]] --] = ip[i];
rep(i, 0, m) nc[i] = 0;
}
void ssort() {
rep(i, 1, n) T[i] = s[i];
sort(T + 1, T + n + 1);
int m = unique(T + 1, T + n + 1) - T - 1;
rep(i, 1, n) rk[i] = lower_bound(T + 1, T + m + 1, s[i]) - T;
for(ri k = 1; k <= n; k <<= 1) {
rep(i, 1, n) {
p1[i] = rk[i];
p2[i] = (i + k <= n) ? rk[i + k] : 0;
}
rsort(n, m);
rk[sa[1]] = m = 1;
rep(i, 2, n) {
if(p1[sa[i]] == p1[sa[i - 1]] && p2[sa[i]] == p2[sa[i - 1]]) m --;
rk[sa[i]] = ++ m;
}
if(m >= n) break;
}
for(ri i = 1, k = 0; i <= n; i ++) {
if(k) k --;
int j = sa[rk[i] - 1];
while(s[i + k] == s[j + k]) k ++;
st[rk[i]][0] = k;
}
rep(j, 1, 19)
for(ri i = 1; i + bit[j] - 1 <= n; i ++)
st[i][j] = min(st[i][j - 1], st[i + bit[j - 1]][j - 1]);
}
inline int lcp(int l, int r) {
if(l == r) return n - sa[l] + 1;
if(l > r) swap(l, r); l ++;
int L = lg[r - l + 1];
return min(st[l][L], st[r - bit[L] + 1][L]);
}
int stk[sid], mi[ssd];
#define ls (o << 1)
#define rs (o << 1 | 1)
inline void build(int o, int l, int r) {
if(l == r) { mi[o] = sa[l]; return; }
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
mi[o] = min(mi[ls], mi[rs]);
}
inline int qry(int o, int l, int r, int ml, int mr) {
if(ml > r || mr < l) return 1e9;
if(ml <= l && mr >= r) return mi[o];
int mid = (l + r) >> 1;
return min(qry(ls, l, mid, ml, mr), qry(rs, mid + 1, r, ml, mr));
}
inline int get_pre(int l, int r, int pos, int L) {
int ret = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(lcp(mid, pos) >= L) r = mid - 1, ret = mid;
else l = mid + 1;
}
return ret;
}
inline int get_suf(int l, int r, int pos, int L) {
int ret = -1;
while(l <= r) {
int mid = (l + r) >> 1;
if(lcp(mid, pos) >= L) l = mid + 1, ret = mid;
else r = mid - 1;
}
return ret;
}
inline int solve(int l, int L) {
int pre = get_pre(1, l, l, L);
int suf = get_suf(l, n, l, L);
return qry(1, 1, n, pre, suf);
}
inline int L(int x) {
if(!x) return 0;
return n - sa[x] + 1;
}
int main() {
init();
S = read(); n = read();
if(S == 26) {
scanf("%s", t + 1);
rep(i, 1, n) s[i] = t[i];
}
else rep(i, 1, n) s[i] = read();
s[0] = s[n + 1] = -1;
ssort();
build(1, 1, n);
rep(i, 1, n)
if(L(i) > L(stk[top])) stk[++ top] = i;
rep(i, 1, top) {
int l = L(stk[i - 1]) + 1, r = L(stk[i]);
rep(j, l, r) printf("%d ", solve(stk[i], j));
}
printf("\n");
return 0;
}