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

代码：

  1 //#include"bits/stdc++.h"
  2 #include"cstdio"
  3 #include"map"
  4 #include"set"
  5 #include"cmath"
  6 #include"queue"
  7 #include"vector"
  8 #include"string"
  9 #include"cstring"
 10 #include"ctime"
 11 #include"iostream"
 12 #include"cstdlib"
 13 #include"algorithm"
 14 #define db double
 15 #define ll long long
 16 #define ull unsigned long long
 17 #define vec vector<ll>
 18 #define mt  vector<vec>
 19 #define ci(x) scanf("%d",&x)
 20 #define cd(x) scanf("%lf",&x)
 21 #define cl(x) scanf("%lld",&x)
 22 #define pi(x) printf("%d
",x)
 23 #define pd(x) printf("%f
",x)
 24 #define pl(x) printf("%lld
",x)
 25 //#define rep(i, x, y) for(int i=x;i<=y;i++)
 26 #define rep(i, n) for(int i=0;i<n;i++)
 27 using namespace std;
 28 const int N   = 2e5 + 5;
 29 const int mod = 1e9 + 7;
 30 const int MOD = mod - 1;
 31 const int inf = 0x3f3f3f3f;
 32 const db  PI  = acos(-1.0);
 33 const db  eps = 1e-10;
 34 int sa[N],rev[N];
 35 int r[N];
 36 int tmp[N];
 37 int a[N];
 38 int n,k;
 39 int p1,p2;
 40 bool cmp(int i,int j){
 41     if(r[i] != r[j]) return r[i]<r[j];
 42     else
 43     {
 44         int ri=i+k<=n?r[i+k]:-1;
 45         int rj=j+k<=n?r[j+k]:-1;
 46         return ri<rj;
 47     }
 48 }
 49 void bulid(int s[N],int l,int *sa)
 50 {
 51 
 52     for(int i=0;i<=l;i++){
 53         sa[i]=i;
 54         r[i]=i<l?s[i]:-1;
 55     }
 56     for(k=1;k<=l;k*=2){
 57         sort(sa,sa+l+1,cmp);
 58         tmp[sa[0]]=0;
 59         for(int i=1;i<=l;i++){
 60             tmp[sa[i]]=tmp[sa[i-1]]+(cmp(sa[i-1],sa[i])?1:0);
 61         }
 62         for(int i=0;i<=l;i++){
 63             r[i]=tmp[i];
 64         }
 65     }
 66 }
 67 void cal()
 68 {
 69     memset(rev,0, sizeof(rev));
 70     memset(r,0, sizeof(r));
 71     memset(sa,0, sizeof(sa));
 72     reverse_copy(a,a+n,rev);
 73     bulid(rev,n,sa);
 74     for(int i=0;i<=n;i++){
 75         p1=n-sa[i];
 76         if(p1>=1&&n-p1>=2){
 77             break;
 78         }
 79     }
 80     int m=n-p1;
 81     reverse_copy(a+p1,a+n,rev);
 82     reverse_copy(a+p1,a+n,rev+m);
 83     bulid(rev,2*m,sa);
 84     for(int i=0;i<=2*m;i++){
 85         p2=p1+m-sa[i];
 86         if(p2-p1>=1&&n-p2>=1){
 87             break;
 88         }
 89     }
 90     reverse(a,a+p1);
 91     reverse(a+p1,a+p2);
 92     reverse(a+p2,a+n);
 93     for(int i=0;i<n;i++) printf("%d
",a[i]);
 94 }
 95 int main()
 96 {
 97     ci(n);
 98     for(int i=0;i<n;i++) ci(a[i]);
 99     cal();
100     return 0;
101 }