POJ 3581-Sequence(后缀数组)

港控/mmm° 2022-07-19 00:17 138阅读 0赞

Sequence

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;6485</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;1429</td> 
  </tr> 
  <tr> 
   <td colspan="3" align="center" style="color:rgb(14,173,0)"><strong>Case Time Limit:</strong>&nbsp;2000MS</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a sequence, \{ *A*1, *A*2, ..., *An*\} which is guaranteed *A*1 > *A*2, ..., *An*, you are to cut it into three sub-sequences and reverse them separately to form a new one which is the smallest possible sequence in alphabet order.

The alphabet order is defined as follows: for two sequence \{ *A*1, *A*2, ..., *An*\} and \{ *B*1, *B*2, ..., *Bn*\}, we say \{ *A*1, *A*2, ..., *An*\} is smaller than \{ *B*1, *B*2, ..., *Bn*\} if and only if there exists such *i* ( 1 ≤ *i* ≤ *n*) so that we have *Ai* < *Bi and Aj* = *Bj* for each *j* < *i*.

Input

The first line contains *n.* (*n* ≤ 200000)

The following *n* lines contain the sequence.

Output

output *n* lines which is the smallest possible sequence obtained.

Sample Input

5
    10
    1
    2
    3
    4

Sample Output

1
    10
    2
    4
    3

Hint

\{10, 1, 2, 3, 4\} -> \{10, 1 | 2 | 3, 4\} -> \{1, 10, 2, 4, 3\}

Source

[POJ Founder Monthly Contest – 2008.04.13][POJ Founder Monthly Contest _ 2008.04.13], Yao Jinyu

## 题目意思： ##

有一个数组，分割成三份，每份翻转后，得到的最小的字典序?

## 解题思路： ##

后缀数组。先确定第一段，因为A1是最大的，所以求反转之后字符串中字典序最小的后缀。

再将剩余部分分成两段，计算两个原序列并将得到的新序列反转后的后缀数组，从中选取字典序最小的合适的后缀。

cin超时，输入输出外挂WA，scanf才AC…坎坷…

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    #define maxn 200100
    
    int n,k,a[maxn];
    int rev[maxn],sa[maxn];
    int rank[maxn*2],tmp[maxn*2];
    
    bool compare_sa(int i,int j)//倍增法，比较rank
    {
        if(rank[i]!=rank[j]) return rank[i]<rank[j];
        else
        {
            int ri=i+k<=n?rank[i+k] :-1;
            int rj=j+k<=n?rank[j+k] :-1;
            return ri<rj;
        }
    }
    
    void construct_sa(int s[],int N,int sa[])//计算s的后缀数组
    {
        for(int i=0; i<=N; ++i)//初始长度为1，rank为字符编码
        {
            sa[i]=i;
            rank[i]=i<N?s[i] :-1;
        }
        for(k=1; k<=N; k*=2)//倍增法求后缀数组
        {
            sort(sa,sa+N+1,compare_sa);
            tmp[sa[0]]=0;
            for(int i=1; i<=N; ++i)
                tmp[sa[i]]=tmp[sa[i-1]]+(compare_sa(sa[i-1],sa[i])?1:0);
            for(int i=0; i<=N; ++i)
                rank[i]=tmp[i];
        }
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        cin>>n;
        for(int i=0; i<n; ++i)
            cin>>a[i];
        //solve();
        reverse_copy(a,a+n,rev);//a不变，反转a之后存入rev数组
        construct_sa(rev,n,sa);//求后缀数组
        int p1;
        for(int i=0; i<n; ++i)//确定第一段的分割位置
        {
            p1=n-sa[i];
            if((p1>=1)&&n-p1>=2) break;
        }
        //cout<<"p1="<<p1<<endl;
        int m=n-p1;
        reverse_copy(a+p1,a+n,rev);
        reverse_copy(a+p1,a+n,rev+m);
        construct_sa(rev,m*2,sa);
        int p2;
        for(int i=0; i<=2*m; ++i)//确定第二段的分割位置
        {
            p2=p1+m-sa[i];
            if((p2-p1>=1)&&n-p2>=1) break;
        }
        //cout<<"p2="<<p2<<endl;
        reverse(a,a+p1);
        reverse(a+p1,a+p2);
        reverse(a+p2,a+n);
        for(int i=0; i<n; ++i)
            cout<<a[i]<<endl;
        return 0;
    }
    
    /**
    5
    10
    1
    2
    3
    4
    **/

[POJ Founder Monthly Contest _ 2008.04.13]: http://poj.org/searchproblem?field=source&key=POJ+Founder+Monthly+Contest+%E2%80%93+2008.04.13