如果字符集无限大的话直接按照 $sa$ 的顺序依次填即可.
由于字符集非常小，所以要尽量填相同的字符.
我们知道 $sa$ 数组，也就知道了 $rank$ 数组.
那么考虑添加排名为 $i$ 的字符：
如果 $rank[sa[i-1]+1]>rank[sa[i]+1]$，说明 $sa[i]$ 的字典序必须比 $sa[i-1]$ 的字典序大，新建字符.
否则，就不用新建字符.
这么做下去即可.
code:
#include <bits/stdc++.h> #define N 503000 #define LL long long using namespace std; void setIO(string s) { string in=s+".in"; freopen(in.c_str(),"r",stdin); } char str[N]; int sa[N],rk[N]; int main() { // setIO("input"); int i,j,n; scanf("%d",&n); for(i=1;i<=n;++i) { scanf("%d",&sa[i]); rk[sa[i]]=i; } int ch=0; str[sa[1]]=ch+'a'; for(i=2;i<=n;++i) { if(rk[sa[i]+1]<rk[sa[i-1]+1]) ++ch; if(ch>=27) { printf("-1\n"); return 0; } str[sa[i]]=ch+'a'; } printf("%s",str+1); return 0; }
