POJ 3581 三段字符串(后缀数组)

Sequence

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 7923		Accepted: 1801
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

题意：给一个数列，将其分三段，使得每段分别反转组合后的字典序最小。

思路：P381

代码：

 //#include"bits/stdc++.h"

 #include"cstdio"

 #include"map"

 #include"set"

 #include"cmath"

 #include"queue"

 #include"vector"

 #include"string"

 #include"cstring"

 #include"ctime"

 #include"iostream"

 #include"cstdlib"

 #include"algorithm"

 #define db double

 #define ll long long

 #define ull unsigned long long

 #define vec vector<ll>

 #define mt  vector<vec>

 #define ci(x) scanf("%d",&x)

 #define cd(x) scanf("%lf",&x)

 #define cl(x) scanf("%lld",&x)

 #define pi(x) printf("%d\n",x)

 #define pd(x) printf("%f\n",x)

 #define pl(x) printf("%lld\n",x)

 //#define rep(i, x, y) for(int i=x;i<=y;i++)

 #define rep(i, n) for(int i=0;i<n;i++)

 using namespace std;

 const int N   = 2e5 + ;

 const int mod = 1e9 + ;

 const int MOD = mod - ;

 const int inf = 0x3f3f3f3f;

 const db  PI  = acos(-1.0);

 const db  eps = 1e-;

 int sa[N],rev[N];

 int r[N];

 int tmp[N];

 int a[N];

 int n,k;

 int p1,p2;

 bool cmp(int i,int j){

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

     else

     {

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

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

         return ri<rj;

     }

 }

 void bulid(int s[N],int l,int *sa)

 {

     for(int i=;i<=l;i++){

         sa[i]=i;

         r[i]=i<l?s[i]:-;

     }

     for(k=;k<=l;k*=){

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

         tmp[sa[]]=;

         for(int i=;i<=l;i++){

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

         }

         for(int i=;i<=l;i++){

             r[i]=tmp[i];

         }

     }

 }

 void cal()

 {

     memset(rev,, sizeof(rev));

     memset(r,, sizeof(r));

     memset(sa,, sizeof(sa));

     reverse_copy(a,a+n,rev);

     bulid(rev,n,sa);

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

         p1=n-sa[i];

         if(p1>=&&n-p1>=){

             break;

         }

     }

     int m=n-p1;

     reverse_copy(a+p1,a+n,rev);

     reverse_copy(a+p1,a+n,rev+m);

     bulid(rev,*m,sa);

     for(int i=;i<=*m;i++){

         p2=p1+m-sa[i];

         if(p2-p1>=&&n-p2>=){

             break;

         }

     }

     reverse(a,a+p1);

     reverse(a+p1,a+p2);

     reverse(a+p2,a+n);

     for(int i=;i<n;i++) printf("%d\n",a[i]);

 }

 int main()

 {

     ci(n);

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

     cal();

     return ;

 }

巴特西

POJ 3581 三段字符串(后缀数组)

最新文章

热门文章