Given a sequence, {A1, A2, ..., An} which is guaranteed A1 > A2, ..., An, you are to cut it into three sub-sequences and reverse them separately to form a new one which is the smallest possible sequence in alphabet order.
The alphabet order is defined as follows: for two sequence {A1, A2, ..., An} and {B1, B2, ..., Bn}, we say {A1, A2, ..., An} is smaller than {B1, B2, ..., Bn} if and only if there exists such i ( 1 ≤ i ≤ n) so that we have Ai < Bi and Aj = Bj for each j < i.
Input
The first line contains n. (n ≤ 200000)
The following n lines contain the sequence.
Output
output n lines which is the smallest possible sequence obtained.
Sample Input
5 10 1 2 3 4
Sample Output
1 10 2 4 3
题意:
分成三个非空段,分别翻转,求字典序最小的方案.
思路:
将其翻转,找到字典序最小的后缀,要求起点在[0,n-2) 内,即可找到第一段.
第一段去除之后,对原串翻转,并复制,找到字典序最小的,即可找到第二段和第三段.
假设原串是 ab
翻转复制后:b'a'b'a'
a'b'就是最终的结果,所以这样做是正确的.
当然要注意后缀起点位置.
#include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<cstdio> #include<cstring> #include<cmath> #include<ctime> #define fuck(x) cerr<<#x<<" = "<<x<<endl; #define debug(a, x) cerr<<#a<<"["<<x<<"] = "<<a[x]<<endl; #define ls (t<<1) #define rs ((t<<1)|1) using namespace std; typedef long long ll; typedef unsigned long long ull; const int maxn = 200086; const int maxm = 100086; const int inf = 0x3f3f3f3f; const ll Inf = 999999999999999999; const int mod = 1000000007; const double eps = 1e-6; const double pi = acos(-1); int s[maxn]; int len, Rank[maxn], sa[maxn], tlen, tmp[maxn]; bool compare_sa(int i, int j) { if (Rank[i] != Rank[j]) { return Rank[i] < Rank[j]; } //如果以i开始,长度为k的字符串的长度,已经超出了字符串尾,那么就赋值为-1 //这是因为,在前面所有数据相同的情况下,字符串短的字典序小. int ri = i + tlen <= len ? Rank[i + tlen] : -inf; int rj = j + tlen <= len ? Rank[j + tlen] : -inf; return ri < rj; } void construct_sa() { //初始的RANK为字符的ASCII码 for (int i = 0; i <= len; i++) { sa[i] = i; Rank[i] = i < len ? s[i] : -inf; } for (tlen = 1; tlen <= len; tlen *= 2) { sort(sa, sa + len + 1, compare_sa); tmp[sa[0]] = 0; //全新版本的RANK,tmp用来计算新的rank //将字典序最小的后缀rank计为0 //sa之中表示的后缀都是有序的,所以将下一个后缀与前一个后缀比较,如果大于前一个后缀,rank就比前一个加一. //否则就和前一个相等. for (int i = 1; i <= len; i++) { tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0); } for (int i = 0; i <= len; i++) { Rank[i] = tmp[i]; } } } int height[maxn]; void construct_lcp() { // for(int i=0;i<=n;i++){Rank[sa[i]]=i;} int h = 0; height[0] = 0; for (int i = 0; i < len; i++) {//i为后缀数组起始位置 int j = sa[Rank[i] - 1];//获取当前后缀的前一个后缀(排序后) if (h > 0)h--; for (; j + h < len && i + h < len; h++) { if (s[j + h] != s[i + h])break; } height[Rank[i]] = h; } } int st[maxn][20]; void rmq_init() { for (int i = 1; i <= len; i++) { st[i][0] = height[i]; } int l = 2; for (int i = 1; l <= len; i++) { for (int j = 1; j + l / 2 <= len; j++) { st[j][i] = min(st[j][i - 1], st[j + l / 2][i - 1]); } l <<= 1; } } int ask_min(int i, int j) { int k = int(log(j - i + 1.0) / log(2.0)); return min(st[i][k], st[j - (1 << k) + 1][k]); } int lcp(int a, int b)//此处参数是,原字符串下标 { a = Rank[a], b = Rank[b]; if (a > b) swap(a, b); return ask_min(a + 1, b); } int solve(int l, int r) { int ans = 0; for (int i = 1; i <= len; i++) { // fuck(sa[i]) if (sa[i] >= l && sa[i] <= r) { ans = sa[i]; break; } } return ans; } int num[maxn]; int main() { // ios::sync_with_stdio(false); // freopen("in.txt", "r", stdin); int n; scanf("%d", &n); len = n; for (int i = 0; i < n; i++) { scanf("%d", &s[i]); num[i] = s[i]; } reverse(s, s + n); construct_sa(); int fi = solve(2, n - 1); fi = len - fi - 1; reverse(num, num + fi + 1); len = 0; for (int i = fi + 1; i < n; i++) { s[len++] = num[i]; } reverse(s, s + len); for(int i=0;i<len;i++){ s[i+len]=s[i]; }len*=2; construct_sa(); int se = solve(1, len /2-1); se = n - se - 1; reverse(num + fi + 1, num + se + 1); reverse(num + se + 1, num + n); for (int i = 0; i < n; i++) { printf("%d ", num[i]); } return 0; }