BZOJ2882: 工艺(后缀数组)
程序员文章站
2022-05-25 19:58:10
题意 "题目链接" Sol 直接把序列复制一遍 后缀数组即可 在前$N$个位置中取$rak$最小的输出 cpp include using namespace std; const int MAXN = 1e6 + 10; inline int read() { char c = getchar() ......
题意
sol
直接把序列复制一遍
后缀数组即可
在前\(n\)个位置中取\(rak\)最小的输出
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; 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 n, m, tax[maxn], tp[maxn], rak[maxn], sa[maxn], a[maxn]; void qsort() { 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[tax[rak[tp[i]]]--] = tp[i]; } void suffixsort() { for(int i = 1; i <= n; i++) tp[i] = i, rak[i] = a[i]; qsort(); for(int w = 1, p; p < n; w <<= 1, m = p) { p = 0; for(int i = 1; i <= w; i++) tp[++p] = n - w + i; for(int i = 1; i <= n; i++) if(sa[i] > w) tp[++p] = sa[i] - w; qsort(); swap(tp, rak); 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; } } int main() { m = n = read(); for(int i = 1; i <= n; i++) a[i] = a[i + n] = read(); n <<= 1; suffixsort(); // for(int i = 1; i <= n; i++) printf("%d ", rak[i]); int mx; rak[mx = 0] = 1e9 + 10; for(int i = 1; i <= n / 2; i++) if(rak[i] < rak[mx]) mx = i; for(int i = mx; i <= mx + n / 2 - 1; i++) printf("%d ", a[i]); return 0; } /* 4 2 2 1 2 10 10 9 8 7 1 6 5 4 3 2 20 10 9 8 7 6 5 4 3 2 1 10 9 8 7 6 5 4 3 2 1 */