[POJ3581]Sequence
题目大意：
给定序列\(A_{1\sim n}\)，其中\(A_1\)为最大的数。要把这个序列分成\(3\)个非空段，并将每一段分别反转，求能得到的字典序最小的序列。
思路：
对于第一段，由于\(A_1\)是最大的数字，因此我们可以将\(A_{1\sim n}\)翻转，用后缀数组求最小后缀作为第一段。
对于剩下两段，如果仍然套用第一段的方法是行不通的。下面是反例：
9
8 4 -1 5 0 5 0 2 3
显然，该序列翻转后为3 2 0 5 0 5 -1 4 8。最小后缀为-1 4 8，作为第一段翻转后的值是最优的。
对于剩下两段，3 2 0 5 0 5的最小后缀为0 5，此时最终答案就变成了-1 4 8 0 5 3 2 0 5，而我们不难发现最优解其实是-1 4 8 0 5 0 5 3 2。
那么，问题出在哪里呢？
事实上，题目让我们求的是操作后整个序列字典序最小，因此我们在计算第二段是也需要考虑第三段的影响。我们不妨将去掉第一段后剩下的序列复制两遍接起来，求起点在前面一半的最小后缀。还是以上文的数据为例，将3 2 0 5 0 5改成3 2 0 5 0 5 3 2 0 5 0 5。此时我们求得最小后缀为0 5 0 5 3 2 0 5 0 5。第二段为0 5 0 5，第三段为3 2。因此得到最后序列为-1 4 8 0 5 0 5 3 2。
使用倍增+快排的后缀数组，时间复杂度是\(\mathcal O(n\log^2 n)\)的。
源代码：
#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
register char ch;
register bool neg=false;
while(!isdigit(ch=getchar())) neg|=ch=='-';
register int x=ch^'0';
while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
return neg?-x:x;
}
const int N=2e5;
int n,k,a[N],sa[N*2],rank[N*2],tmp[N*2],rev[N*2];
inline bool cmp(const int &i,const int &j) {
if(rank[i]!=rank[j]) return rank[i]<rank[j];
const int ri=i+k<n?rank[i+k]:-1;
const int rj=j+k<n?rank[j+k]:-1;
return ri<rj;
}
inline void suffix_sort(const int &nn) {
n=nn;
for(register int i=0;i<n;i++) {
sa[i]=i;
rank[i]=i<n?rev[i]:-1;
}
for(k=1;k<=n;k<<=1) {
std::sort(&sa[0],&sa[n],cmp);
tmp[sa[0]]=0;
for(register int i=1;i<n;i++) {
tmp[sa[i]]=tmp[sa[i-1]]+!!cmp(sa[i-1],sa[i]);
}
for(register int i=0;i<n;i++) {
rank[i]=tmp[i];
}
}
}
int main() {
const int n=getint();
for(register int i=0;i<n;i++) a[i]=getint();
std::reverse_copy(&a[0],&a[n],&rev[0]);
suffix_sort(n);
int p1=0,p2=0;
for(register int i=0;i<n&&(p1<1||n-p1<2);i++) {
p1=n-sa[i];
}
const int m=n-p1;
std::reverse_copy(&a[p1],&a[n],&rev[0]);
std::reverse_copy(&a[p1],&a[n],&rev[m]);
suffix_sort(m*2);
for(register int i=0;i<m*2&&(p2-p1<1||n-p2<1);i++) {
p2=n-sa[i];
}
std::reverse(&a[0],&a[p1]);
std::reverse(&a[p1],&a[p2]);
std::reverse(&a[p2],&a[n]);
for(register int i=0;i<n;i++) {
printf("%d\n",a[i]);
}
return 0;
}