给一串数，将其分成三个区间并且颠倒这三个区间，使得新数列字典序最小。

参考：

（不是论文题，但是还是借鉴了题解，我是真的菜）

首先我们分成的三个区间肯定是一个前缀+中间一段+一个后缀。

那么我们先求前缀，方法很简单，只需要将原数列倒着存，然后找字典序最小的后缀即可。可以用后缀数组实现。

（因为原数列前缀的颠倒肯定是原数列颠倒后的其中一个后缀）

再考虑如何求中间一段。我们先把前面求完的部分扣掉，然后求字典序最小的后缀……？

并不是这样，比如3 5 0 5 0 5，按照这个方法我们得到的是0 5，但实际上我们要得到0 5 0 5。

所以为了避免这种情况，我们将这个数列倍长，这样就能使得0505小于05了。

最后再把剩下的一点输出即可。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;const int N=4e5+10;int n,m,t,rank[N],sa[N],height[N],w[N],b[N],s[N];inline bool pan(int *x,int i,int j,int k){ int ti=i+k
             
              =0;i--)sa[--w[s[i]]]=i; r=1;x[sa[0]]=0; for(int i=1;i
              
               =k)y[yn++]=sa[i]-k; for(int i=0;i
               
                =0;i--)sa[--w[x[y[i]]]]=y[i]; swap(x,y);r=1;x[sa[0]]=0; for(int i=1;i
                
                 =0;i--){ scanf("%d",&b[i]); s[i]=b[i]; } m=n; LSH(); SA_init(); for(t=0;;t++){ if(sa[t]>1)break; } for(int i=sa[t];i
                 
                  >1))break; } for(int i=sa[t];i<(n>>1);i++) printf("%d\n",b[s[i]]); for(int i=0;i
                 
                
               
              
             
            
           
          
         
        
       
      
     

+++++++++++++++++++++++++++++++++++++++++++

 +本文作者：luyouqi233。 　　　　　　　　　　　　　　+

 +欢迎访问我的博客：+

+++++++++++++++++++++++++++++++++++++++++++