poj3581

港控/mmm° 2021-10-26 13:50 202阅读 0赞

Sequence

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong> 5000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong> 65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong> 6893</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong> 1534</td> 
  </tr> 
  <tr> 
   <td style="color:#0ead00;" colspan="3" align="center"><strong>Case Time Limit:</strong> 2000MS</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a sequence, \{ *A*1, *A*2, ..., *An*\} which is guaranteed *A*1 > *A*2, ..., *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 \{ *A*1, *A*2, ..., *An*\} and \{ *B*1, *B*2, ..., *Bn*\}, we say \{ *A*1, *A*2, ..., *An*\} is smaller than \{ *B*1, *B*2, ..., *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\}

白书上的题目。第一道后缀数组，直接看了答案，但是没看懂。。。

第一段翻转很好求，直接翻转然后后缀数组。第二段第三段则有些问题，因为可能第二段比较短，虽然最小，但是是其他某个串的前缀，可能会出错（自己yy的，网上有反例）

--------------------

9  
8 4 -1 5 0 5 0 2 3  
第一步：  
3 2 0 5 0 5 -1 4 8 对应输出 -1 4 8  
第二步  
3 2 0 5 0 5（开始的时候我并没有复制一遍） 对应输出：0 5  
第三步  
3 2 0 5    对应输出： 3 2 0 5  
可以看见这样做是不对的。。  
必须要将剩下的字符串复制一遍贴在后面，然后再来求后缀数组。。。  
正解：  
第一步：  
3 2 0 5 0 5 -1 4 8 对应输出 -1 4 8  
第二步  
3 2 0 5 0 5 3 2 0 5 0 5 对应输出： 0 5 0 5；  
第三步  
3 2 对应输出：3 2；

最后值得注意的是此题还要用离散化。。因为并没有告诉我们输入的数据有多大。。。。。（其实不用离散化，离散化是因为用的基数排序，快排就没这个问题了）

--------------------

然后就是把第一段截掉剩余的东西翻转，复制一遍接在后面，再做后缀数组。

程序里的第二个循环值得注意，当p2=m-sa\[i\]+1+p1 p1<p2<n时成立退出，为什么是这个式子？这里我也不太懂，但是我们可以发现，当sa\[i\]位于复制后的字符串的前一段是才可以，那么sa\[i\]肯定是小于m的，

8 7 6 5 4 3 8 7 6 5 4 3 sa\[i\]=3

注意,是sa\[i\]=3,所以我们截得的字符串不是8 7 6和5 4 3 而是8 7和6 5 4 3，因为sa\[i\]表示的是这个位置到结尾的后缀。所以我们的第二串长度是m-sa\[i\]+1,在原串中的位置是p1+len=p1+m-sa\[i\]+1

那么我们可以发现p1<p2<n。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    #define N 400010
    int n,m,k;
    int a[N],rank[N],temp[N],sa[N],rev[N];
    bool cp(int i,int j)
    {
        if(rank[i]!=rank[j]) return rank[i]<rank[j];
        int ri=i+k<=n?rank[i+k]:-1;
        int rj=j+k<=n?rank[j+k]:-1;
        return ri<rj;
    }
    void Sa(int a[],int n)
    {
        for(int i=1;i<=n;i++)
        {
            sa[i]=i; rank[i]=a[i];
        }
        for(k=1;k<=n;k*=2)
        {
            sort(sa+1,sa+n+1,cp);
            temp[sa[1]]=1;
            for(int i=1;i<=n;i++)
                temp[sa[i]]=temp[sa[i-1]]+(cp(sa[i-1],sa[i]));
            for(int i=1;i<=n;i++) rank[i]=temp[i];
        }
    }
    void solve()
    {
        reverse_copy(a+1,a+n+1,rev+1);
        Sa(rev,n);
        int p1=0;
        for(int i=1;i<=n;i++)
        {
            p1=n-sa[i]+1;
            if(p1>0&&n-p1>=2) break;
        }
        memset(rev,0,sizeof(rev));
        int m=n-p1;
        reverse_copy(a+p1+1,a+n+1,rev+1);
        reverse_copy(a+p1+1,a+n+1,rev+m+1);
        Sa(rev,2*m);
        int p2=0;
        for(int i=1;i<=2*m;i++)
        {
            p2=m-sa[i]+1+p1;
            if(p2>p1&&p2<n) break;
        }
        for(int i=p1;i>=1;i--) printf("%d\n",a[i]);
        for(int i=p2;i>p1;i--) printf("%d\n",a[i]);
        for(int i=n;i>p2;i--) printf("%d\n",a[i]);
    }
    int main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        solve();
        return 0;
    }

转载于:https://www.cnblogs.com/19992147orz/p/6254142.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211026/1921a932dbdc452584cd9feb752d2264.png