题意
给出n个数字的序列，现在让你分成三段，使得每一段翻转之后拼接起来的序列字典序最小。保证第一个数是序列中最大的数。
例如样例是{10, 1, 2, 3, 4}，分成{1, 10}, {2}, {3,4}，最后字符串变成{1, 10, 2, 4, 3}。
思路
首先考虑第一段，因为第一个数是最大的，因此只要使得某一个前缀翻转后的字典序最小，所以只要选择序列翻转后最小后缀。
对于第二段和第三段，如果像第一段一样直接找剩下的里面最小的后缀，是不可行的，因为直接取第二段最优就忽略了第三段的最优。
例如对于这个剩下的序列：{3, 1, 2, 3, 1, 4}，翻转后：{4, 1, 3, 2, 1, 3}，取最小后缀{1, 3}作为第二段，那么最后得到的第二三段翻转后的后缀合起来是：{1, 3, 4, 1, 3, 2}。
这样不如取后缀{1, 3, 2, 1, 3}作为第二段更优，最后得到{1, 3, 2, 1, 3, 4}。
可以发现，这是一个类似于环的东西，即第一段取了{1,3}，剩下一段{4, 1, 3, 2}就是接在{1,3}后面的，构成了一个环状的序列。
那么现在问题就转化为，求一个环状序列长度为n的字典序最小序列了。
因此，可以直接复制一遍序列放在后面，变成{4, 1, 3, 2, 1, 3, 4, 1, 3, 2, 1, 3}，这样再对这个序列求一个最小后缀（这个最小后缀要合法），得到的就是可行的了。
回过头来，为什么第一段就可以直接求？
因为第一个数是最大的，像个墙一样卡在那里，如果也是复制一遍的话，可以发现其实根本取不到后面（取[n,2*n)的字典序不可能比取[0,n)的后缀更小）。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 11;
int t1[N*2], t2[N*2], c[N*2], s[N*2], str[N*2], Hash[N], sa[N*2], n;
bool cmp(int *r, int a, int b, int l) {
return r[a] == r[b] && r[a+l] == r[b+l];
}
void SA(int s[], int sa[], int n, int m) {
int i, j, p, *x = t1, *y = t2;
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[i] = s[i]]++;
for(i = 1; i < m; i++) c[i] += c[i-1];
for(i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
for(j = 1; j <= n; j <<= 1) {
p = 0;
for(i = n - j; i < n; i++) y[p++] = i;
for(i = 0; i < n; i++) if(sa[i] >= j) y[p++] = sa[i] - j;
for(i = 0; i < m; i++) c[i] = 0;
for(i = 0; i < n; i++) c[x[y[i]]]++;
for(i = 1; i < m; i++) c[i] += c[i-1];
for(i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1; x[sa[0]] = 0;
for(i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1 : p++;
if(p >= n) break;
m = p;
}
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) scanf("%d", &s[i]), Hash[i] = s[i];
sort(Hash, Hash + n);
int m = unique(Hash, Hash + n) - Hash;
// 离散化后注意区间是到m不是到n !!!
for(int i = 0; i < n; i++) s[i] = lower_bound(Hash, Hash + m, s[i]) - Hash;
int p1, p2;
reverse_copy(s, s + n, str);
SA(str, sa, n, m);
for(int i = 0; i < n; i++) {
p1 = n - sa[i];
if(p1 >= 1 && n - p1 >= 2) break;
// 第一段至少有1个数并且剩下至少两个数(因为后面要分成两段)
}
int nn = n - p1;
reverse_copy(s + p1, s + n, str);
reverse_copy(s + p1, s + n, str + nn);
SA(str, sa, 2 * nn, m);
for(int i = 0; i < 2 * nn; i++) {
if(sa[i] >= nn) continue;
p2 = nn - sa[i] + p1;
if(p2 - p1 >= 1 && n - p2 >= 1) break;
// 第二段至少有1个数并且至少剩下一个数(还剩下一段)
}
for(int i = p1 - 1; i >= 0; i--) printf("%d
", Hash[s[i]]);
for(int i = p2 - 1; i >= p1; i--) printf("%d
", Hash[s[i]]);
for(int i = n - 1; i >= p2; i--) printf("%d
", Hash[s[i]]);
return 0;
}
/*
8
5 0 3 1 2 3 1 4
0
5
1
3
2
1
3
4
*/