题目大意

给定后缀数组sa,要求构造出满足sa数组的字符串.或输出无解\(n\leq 5*10^5\)

题解

我们按照字典序来考虑每个后缀

对于\(Suffix(sa[i])\)和\(Suffix(sa[i-1])\)

我们一定知道\(Suffix(sa[i-1])<Suffix(sa[i])\).

如果我们有\(Suffix(sa[i-1]+1)<Suffix(sa[i]+1)\)

那么\(sa[i]\)和\(sa[i-1]\)两个位置上的字符相等时也满足条件

那么从贪心的角度来讲我们就让\(sa[i] = sa[i-1]\)

如果我们有\(Suffix(sa[i-1]+1)>Suffix(sa[i]+1)\)

那么就必须有\(sa[i-1]\)上的字符\(<\) \(sa[i]\)上的字符了

对于这个后缀的大小判断我们直接使用\(rank\)数组即可

Code

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;inline void read(int &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a
        rank[sa[i]+1]) ++ nw;        if(nw > 'z') return puts("-1");        s[sa[i]] = nw;    }s[n+1] = '\0';    printf("%s\n",s+1);    getchar();getchar();    return 0;}