POJ 3581 Sequence [后缀数组]

时间：2023-03-08 20:20:26
Sequence
Time Limit: 5000MS   Memory Limit: 65536K
Total Submissions: 6911   Accepted: 1543
Case Time Limit: 2000MS

Description

Given a sequence, {A1, A2, ..., An} which is guaranteed A1 > A2, ..., 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 {A1, A2, ..., An} and {B1, B2, ..., Bn}, we say {A1, A2, ..., An} is smaller than {B1, B2, ..., 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

题意：

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

字符串反转后求最小后缀就是第一段啦
后两段的话，保持反转不变，然后复制一份接在后面求最小后缀就行了，自己画图看看吧
注意判断位置的合法性，比如需要分成三份，以及第二次不能分在复制的那一份上
还有，需要离散化........
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int N=2e5+,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,m,c[N],t1[N],t2[N];

int s[N],mp[N];

void iniMP(){

    sort(mp+,mp++n);

    int p=;mp[++p]=mp[];

    for(int i=;i<=n;i++) if(mp[i]!=mp[i-]) mp[++p]=mp[i];

    mp[]=p;

}

int Bin(int v){

    int l=,r=mp[];

    while(l<=r){

        int mid=(l+r)>>;

        if(v==mp[mid]) return mid;

        else if(v<mp[mid]) r=mid-;

        else l=mid+;

    }

    return ;

}

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[];

    int *r=t1,*k=t2;

    for(int i=;i<=m;i++) c[i]=;

    for(int i=;i<=n;i++) c[r[i]=s[i]]++;

    for(int i=;i<=m;i++) c[i]+=c[i-];

    for(int i=n;i>=;i--) sa[c[r[i]]--]=i;

    for(int j=;j<=n;j<<=){

        int p=;

        for(int i=n-j+;i<=n;i++) k[++p]=i;

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

        for(int i=;i<=m;i++) c[i]=;

        for(int i=;i<=n;i++) c[r[k[i]]]++;

        for(int i=;i<=m;i++) c[i]+=c[i-];

        for(int i=n;i>=;i--) sa[c[r[k[i]]]--]=k[i];

        swap(r,k);p=;r[sa[]]=++p;

        for(int i=;i<=n;i++) r[sa[i]]=cmp(k,sa[i],sa[i-],j)?p:++p;

        if(p>=n) break;m=p;

    }

}

void solve(){

    reverse(s+,s++n);

    getSA(s);

    int p=;

    while(sa[p]<=) p++;

    for(int i=sa[p];i<=n;i++) printf("%d\n",mp[s[i]]);

    n=sa[p]-;

    for(int i=;i<=n;i++) s[i+n]=s[i];

    n<<=;

    getSA(s);

    p=;

    n>>=;

    while(sa[p]==||sa[p]>n) p++;

    for(int i=sa[p];i<=n;i++) printf("%d\n",mp[s[i]]);

    for(int i=;i<sa[p];i++) printf("%d\n",mp[s[i]]);

}

int main(){

    freopen("in","r",stdin);

    n=read();

    for(int i=;i<=n;i++) s[i]=mp[i]=read();

    iniMP();

    for(int i=;i<=n;i++) s[i]=Bin(s[i]);

    solve();

}

相关文章