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

Sample Output

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[],b[],c[],sa[],rk[],tmp[];

int cmp(int i,int j)

{

    if(rk[i]!=rk[j]) return rk[i]<rk[j];

    int ri=i+k<=n?rk[i+k]:-;

    int rj=j+k<=n?rk[j+k]:-;

    return ri<rj;

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        b[n-i]=a[i];

    }

    for(int i=;i<n;i++)

    {

        sa[i]=i;

        rk[i]=b[i];

    }

    sa[n]=n;

    rk[n]=-;

    for(k=;k<=n;k<<=)

    {

        sort(sa,sa+n+,cmp);

        tmp[sa[]]=;

        for(int i=;i<=n;i++)

        {

            tmp[sa[i]]=tmp[sa[i-]]+cmp(sa[i-],sa[i]);

        }

        for(int i=;i<=n;i++)

        {

            rk[i]=tmp[i];

        }

    }

    sort(sa,sa+n+,cmp);

    for(int i=;i<=n;i++)

    {

        if(sa[i]!=&&sa[i]!=&&sa[i]!=n)

        {

            pos=sa[i];

            break;

        }

    }

    int len=n-pos;

    int cnt=;

    for(int i=n;i>=len+;i--)

    {

        c[cnt++]=a[i];

    }

    for(int i=cnt;i<cnt*;i++)

    {

        c[i]=c[i-cnt];

    }

    n=cnt*;

    for(int i=;i<n;i++)

    {

        sa[i]=i;

        rk[i]=c[i];

    }

    sa[n]=n;

    rk[n]=-;

    for(k=;k<=n;k<<=)

    {

        sort(sa,sa+n+,cmp);

        tmp[sa[]]=;

        for(int i=;i<=n;i++)

        {

            tmp[sa[i]]=tmp[sa[i-]]+cmp(sa[i-],sa[i]);

        }

        for(int i=;i<=n;i++)

        {

            rk[i]=tmp[i];

        }

    }

    for(int i=len;i>=;i--)

    {

        printf("%d\n",a[i]);

    }

    sort(sa,sa+n+,cmp);

    for(int i=;i<=n;i++)

    {

        if(sa[i]+n/<n&&sa[i]!=)

        {

            for(int j=sa[i];j<=sa[i]+n/-;j++)

            {

                printf("%d\n",c[j]);

            }

            break;

        }

    }

}

巴特西

POJ 3581 Sequence(后缀数组）

最新文章

热门文章