POJ 3581 Sequence [后缀数组]

Sequence

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 6911		Accepted: 1543
Case Time Limit: 2000MS

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}

Source

POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu

题意：

给出一个字符串，要求将其切成3段，然后将每段翻转，使得得到的新串字典序最小
保证原串第一个字符的字典序比后面的都大

字符串反转后求最小后缀就是第一段啦

后两段的话，保持反转不变，然后复制一份接在后面求最小后缀就行了，自己画图看看吧

注意判断位置的合法性，比如需要分成三份，以及第二次不能分在复制的那一份上

还有，需要离散化........

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=2e5+5,INF=1e9;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    return x*f;
}
int n,m,c[N],t1[N],t2[N];
int s[N],mp[N];
void iniMP(){
    sort(mp+1,mp+1+n);
    int p=0;mp[++p]=mp[1];
    for(int i=2;i<=n;i++) if(mp[i]!=mp[i-1]) mp[++p]=mp[i];
    mp[0]=p;
}
int Bin(int v){
    int l=1,r=mp[0];
    while(l<=r){
        int mid=(l+r)>>1;
        if(v==mp[mid]) return mid;
        else if(v<mp[mid]) r=mid-1;
        else l=mid+1;
    }
    return 0;
}

int sa[N],rnk[N],height[N];
inline bool cmp(int *r,int a,int b,int j){
    return a+j<=n&&b+j<=n&&r[a]==r[b]&&r[a+j]==r[b+j];
}
void getSA(int s[]){
    m=mp[0];
    int *r=t1,*k=t2;
    for(int i=0;i<=m;i++) c[i]=0;
    for(int i=1;i<=n;i++) c[r[i]=s[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i>=1;i--) sa[c[r[i]]--]=i;

    for(int j=1;j<=n;j<<=1){
        int p=0;
        for(int i=n-j+1;i<=n;i++) k[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>j) k[++p]=sa[i]-j;

        for(int i=0;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[r[k[i]]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[r[k[i]]]--]=k[i];

        swap(r,k);p=0;r[sa[1]]=++p;
        for(int i=2;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-1],j)?p:++p;
        if(p>=n) break;m=p;
    }
}

void solve(){
    reverse(s+1,s+1+n);
    getSA(s);
    int p=1;
    while(sa[p]<=2) p++;
    for(int i=sa[p];i<=n;i++) printf("%d
",mp[s[i]]);

    n=sa[p]-1;
    for(int i=1;i<=n;i++) s[i+n]=s[i];
    n<<=1;
    getSA(s);
    p=1;
    n>>=1;
    while(sa[p]==1||sa[p]>n) p++;
    for(int i=sa[p];i<=n;i++) printf("%d
",mp[s[i]]);
    for(int i=1;i<sa[p];i++) printf("%d
",mp[s[i]]);
}

int main(){
    freopen("in","r",stdin);
    n=read();
    for(int i=1;i<=n;i++) s[i]=mp[i]=read();
    iniMP();
    for(int i=1;i<=n;i++) s[i]=Bin(s[i]);
    solve();
}