题意：
把数组分成3分，每一份都翻转，要求输出字典序最小的结果
思路：
保证第一个数最大，所以第一部分直接找字典序最小的。（SA第一遍）
其后由于只需把剩下的串分成两部分，所以不需要考虑最后一节，只需保持中间的一节为最小字典序。
故形同求串的最小表示，要将串复制一遍，再求最小字典序。（SA第二遍）
代码：
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> #include <queue> #include <map> using namespace std; const int INF=0x3f3f3f3f; const int MAXN=200020; int hash[MAXN]; int sa[MAXN],m,b[MAXN]; int t1[MAXN],t2[MAXN],c[MAXN]; int rank[MAXN],height[MAXN]; int tem[MAXN]; map <int,int> imap; void build_sa(int s[],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]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++; if(p>=n)break; m=p; } int k = 0; n--; for(i = 0; i <= n; i++) rank[sa[i]] = i; for(i = 0; i < n; i++) { if(k) k--; j = sa[rank[i]-1]; while(s[i+k] == s[j+k]) k++; height[rank[i]] = k; } } int main(){ int n; int s[MAXN]; scanf("%d",&n); imap.clear(); for(int i=0;i<n;i++){ scanf("%d",&b[i]); tem[i]=b[i]; } sort(tem,tem+n); int k=0;int las=-INF; for(int i=0;i<n;i++){ if(las!=tem[i]){ hash[++k]=tem[i]; imap[tem[i]]=k; las=tem[i]; } } for(int i=0;i<n;i++) s[n-1-i]=imap[b[i]]; s[n]=0; build_sa(s,n+1,k+10); int pos=min_element(rank+2,rank+n)-rank; for(int i=pos;i<n;i++) printf("%d\n",hash[s[i]]); for(int i=0;i<=pos;i++) s[pos+i]=s[i]; s[pos*2+1]=0; int len=pos; build_sa(s,len*2+1,k+10); pos=min_element(rank+1,rank+len)-rank; for(int i=pos;i<len;i++) printf("%d\n",hash[s[i]]); for(int i=0;i<pos;i++) printf("%d\n",hash[s[i]]); return 0; }
