[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;

}