[POJ 3581]Sequence

标签： 后缀数组

---

题目链接

题意

给你一串序列\(A_i\)，保证对于$ \forall i \in [2,n],都有A_1 >A_i$。

现在需要把这个序列分成三段，并且将这三段分别翻转，求如何翻转使整个序列字典序最小。（每一段不能为空）

题解

首先可以确定第一段的位置。

注意到，\(A_1\)是最大的，所以我们就只用考虑怎样找到一个前缀使其翻转后的字典序最小。

（假如不是的话，就可能找到两个前缀翻转之后，一个为另一个的前缀，无法解决）

这等价于翻转之后找到一个后缀使其字典序最小，用后缀数组处理一下。

然后确定第二段的位置。

先翻转之后，找一个分割点使整个串最小。这等价于最小循环表示法问题。

可以直接用后缀数组解决，也有O(n)的做法。

Code

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

#include<queue>

#include<stack>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)

#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)

#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)

inline int read()

{

	int sum=0,p=1;char ch=getchar();

	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();

	if(ch=='-')p=-1,ch=getchar();

	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();

	return sum*p;

}

const int maxn=4e5+20;

int n,a[maxn],sa[maxn],S[maxn],cnt;

void init()

{

	n=read();

	REP(i,0,n-1)a[i]=read(),S[cnt++]=a[i];

	sort(S,S+cnt);

	cnt=unique(S,S+cnt)-S;

	REP(i,0,n-1)a[i]=lower_bound(S,S+cnt,a[i])-S;

}

int r[maxn*2];

int x[maxn],y[maxn]={0},bug[maxn]={0},v[maxn*2];

void suffix_array(int *r,int n)

{

	int p=0,m=200000;

	memset(v,-1,sizeof(v));

	REP(i,0,m)bug[i]=0;

	REP(i,0,n-1)bug[x[i]=r[i]]++;

	REP(i,1,m)bug[i]+=bug[i-1];

	DREP(i,n-1,0)sa[--bug[x[i]]]=i;

	for(int j=1;p<n;j*=2,m=p)

	{

		p=0;REP(i,n-j,n-1)y[p++]=i;

		REP(i,0,n-1)if(sa[i]>=j)y[p++]=sa[i]-j;

		REP(i,0,m)bug[i]=0;

		REP(i,0,n-1)bug[v[i]=x[y[i]]]++;

		REP(i,1,m)bug[i]+=bug[i-1];

		DREP(i,n-1,0)sa[--bug[v[i]]]=y[i];

		REP(i,0,n-1)v[i]=x[i];p=1;x[sa[0]]=0;

		REP(i,1,n-1)x[sa[i]]=v[sa[i-1]]==v[sa[i]] && v[sa[i-1]+j]==v[sa[i]+j] ?p-1:p++;

	}

}

void doing()

{

	REP(i,0,n-1)r[i]=a[n-i-1];

	suffix_array(r,n);

	int X=0;

	REP(i,0,n-1)if(sa[i]>1){X=sa[i];break;}

	REP(i,X,n-1)cout<<S[r[i]]<<endl;

	//REP(i,0,n-X-1)x[i]=a[i+X+1];

	n=X;

	REP(i,n,2*n-1)r[i]=r[i-n];

	suffix_array(r,2*n);

	REP(i,0,2*n-1)if(sa[i]<n && sa[i]){X=sa[i];break;}

	REP(i,X,n-1+X)cout<<S[r[i]]<<endl;

}

int main()

{

	init();

	doing();

	return 0;

}