洛谷P5108 仰望半月的夜空(后缀数组)
程序员文章站
2022-07-02 16:36:37
题意 "题目链接" Sol warning:下面这个做法只有95分,本地拍了1w+组都没找到错误我表示十分无能为力 我们考虑每个串的排名去更新答案,显然排名为$1$的后缀的前缀一定是当前长度的字典序最小的答案,但不一定是左端点最小的答案,因此还需要用一个数据结构去维护一下所有可行的左端点。然后枚举所 ......
题意
sol
warning:下面这个做法只有95分,本地拍了1w+组都没找到错误我表示十分无能为力
我们考虑每个串的排名去更新答案,显然排名为\(1\)的后缀的前缀一定是当前长度的字典序最小的答案,但不一定是左端点最小的答案,因此还需要用一个数据结构去维护一下所有可行的左端点。然后枚举所有后缀更新答案就行了。
#include<bits/stdc++.h> using namespace std; const int maxn = 2e6 + 10, ss = 6e5 + 10, inf = 1e9 + 10; template <typename a, typename b> inline bool chmin(a &a, b b){if(a > b) {a = b; return 1;} return 0;} template <typename a, typename b> inline bool chmax(a &a, b b){if(a < b) {a = b; return 1;} return 0;} inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int charset, n, m, ans[ss]; int s[ss]; char stmp[ss]; int rak[ss], tp[ss], tax[maxn * 10], sa[ss], height[ss]; void sort() { for(int i = 0; i <= m; i++) tax[i] = 0; for(int i = 1; i <= n; i++) tax[rak[i]]++; for(int i = 1; i <= m; i++) tax[i] += tax[i - 1]; //for(int i = n; i >= 1; i--) sa[i] = tp[tax[rak[i]]--]; for(int i = n; i >= 1; i--) sa[tax[rak[tp[i]]]--] = tp[i]; } void suffixarrarybuild() { m = charset; for(int i = 1; i <= n; i++) rak[i] = s[i], tp[i] = i; sort(); for(int w = 1, p; w < n; w <<= 1, m = p) { p = 0; for(int i = n - w + 1; i <= n; i++) tp[++p] = i; for(int i = 1; i <= n; i++) if(sa[i] > w) tp[++p] = sa[i] - w; sort(); swap(rak, tp); rak[sa[1]] = p = 1; for(int i = 2; i <= n; i++) rak[sa[i]] = (tp[sa[i]] == tp[sa[i - 1]] && tp[sa[i] + w] == tp[sa[i - 1] + w] ? p : ++p); } for(int i = 1, k = 0; i <= n; i++) { int j = sa[rak[i] - 1]; if(k) k--; while(j && s[i + k] == s[j + k]) k++;//mmp一开始没写j.. height[rak[i]] = k;//tag } } #define ls k << 1 #define rs k << 1 | 1 int mn[maxn]; void update(int k) { mn[k] = min(mn[ls], mn[rs]); } void build(int k, int l, int r) { if(l == r) {mn[k] = sa[l]; return ;} int mid = l + r >> 1; build(ls, l, mid); build(rs, mid + 1, r); update(k); } int intquery(int k, int l, int r, int ql, int qr) { if(ql <= l && r <= qr) return mn[k]; int mid = l + r >> 1; if(ql > mid) return intquery(rs, mid + 1, r, ql, qr); else if(qr <= mid) return intquery(ls, l, mid, ql, qr); else return min(intquery(ls, l, mid, ql, qr), intquery(rs, mid + 1, r, ql, qr)); } int f[maxn][20]; int find(int pos, int cur) {//从pos开始的height,第一个 < cur的位置 if(height[pos] < cur) return pos - 1; for(int i = 19; i >= 1; i--) { while(f[pos][i] >= cur && f[pos][i] <= inf && pos + (1 << i) - 1 <= n) pos = pos + (1 << i) - 1; } return pos; } void solve() { build(1, 1, n); memset(f, 0x3f, sizeof(f)); for(int i = 1; i <= n; i++) f[i][0] = height[i]; for(int j = 1; j <= 19; j++) for(int i = 1; i + (1 << j) - 1<= n; i++) chmin(f[i][j], min(f[i][j - 1], f[i + (1 << j - 1)][j - 1])); int cur = 1;//马上要找的答案 for(int rk = 1; rk <= n; rk++) { if((n - sa[rk] + 1) < cur) continue; int pos = sa[rk]; for(int i = pos + cur - 1; i <= n; i++) { int j = find(rk + 1, cur); ans[cur++] = intquery(1, 1, n, rk, j); } } } signed main() { charset = read(); n = read(); if(charset == 26) { scanf("%s", stmp + 1); for(int i = 1; i <= n; i++) s[i] = stmp[i] - 'a'; } else for(int i = 1; i <= n; i++) s[i] = read(); suffixarrarybuild(); solve(); for(int i = 1; i <= n; i++) cout << ans[i] << ' '; return 0; }