POJ 3581 Sequence(后缀数组）

Description

Given a sequence, {A₁, A₂, ..., A_n} which is guaranteed A₁ > A₂, ..., A_n,  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₁, A₂, ..., A_n} and {B₁, B₂, ..., B_n}, we say {A₁, A₂, ..., A_n} is smaller than {B₁, B₂, ..., B_n} if and only if there exists such i ( 1 ≤ i ≤ n) so that we have A_i < B_{i and} A_j = B_j 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}

题意：将数组划分成三分，分别翻转，求翻转后字典序最小的

 

题解：首先将原数组首尾倒转，后缀数组找出字典序最小的后缀，然后再把剩下的翻转，再用后缀数组找出最小的后缀，然后就稳了

 

代码如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int n,k,pos,a[200020],b[200020],c[400020],sa[400020],rk[400020],tmp[400020];

int cmp(int i,int j)
{
    if(rk[i]!=rk[j]) return rk[i]<rk[j];
    int ri=i+k<=n?rk[i+k]:-1;
    int rj=j+k<=n?rk[j+k]:-1;
    return ri<rj;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[n-i]=a[i];
    }
    for(int i=0;i<n;i++)
    {
        sa[i]=i;
        rk[i]=b[i];
    }
    sa[n]=n;
    rk[n]=-1;
    for(k=1;k<=n;k<<=1)
    {
        sort(sa,sa+n+1,cmp);
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++)
        {
            tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);
        }
        for(int i=0;i<=n;i++)
        {
            rk[i]=tmp[i];
        }
    }
    sort(sa,sa+n+1,cmp);
    for(int i=0;i<=n;i++)
    {
        if(sa[i]!=0&&sa[i]!=1&&sa[i]!=n)
        {
            pos=sa[i];
            break;
        }
    }    
    int len=n-pos;
    int cnt=0;
    for(int i=n;i>=len+1;i--)
    {
        c[cnt++]=a[i];
    }
    for(int i=cnt;i<cnt*2;i++)
    {
        c[i]=c[i-cnt];
    }
    n=cnt*2;
    for(int i=0;i<n;i++)
    {
        sa[i]=i;
        rk[i]=c[i];
    }
    sa[n]=n;
    rk[n]=-1;
    for(k=1;k<=n;k<<=1)
    {
        sort(sa,sa+n+1,cmp);
        tmp[sa[0]]=0;
        for(int i=1;i<=n;i++)
        {
            tmp[sa[i]]=tmp[sa[i-1]]+cmp(sa[i-1],sa[i]);
        }
        for(int i=0;i<=n;i++)
        {
            rk[i]=tmp[i];
        }
    }
    for(int i=len;i>=1;i--)
    {
        printf("%d
",a[i]);
    }
    sort(sa,sa+n+1,cmp);
    for(int i=0;i<=n;i++)
    {
        if(sa[i]+n/2<n&&sa[i]!=0)
        {
            for(int j=sa[i];j<=sa[i]+n/2-1;j++)
            {
                printf("%d
",c[j]);
            }
            break;
        }
    }
}