http://1572m36l09.iask.in:30808/problem/31

首先转化为保留尽量少的段使得字典序最大。考虑逐字符确定，
显然我们可以将相同的连续字符缩在一起。注意到字典序最大的
字符一定会在前缀中保留尽量多次，我们可以将字符相同的连续
段按照出现次数排序，并逐一确定。在确定最后一段时，我们需
要考虑剩余部分后缀对串的大小的影响。使用后缀数组处理，时
间复杂度为 O(|s| log |s|)

#include
#include
#include
#include
#include
using namespace std;
;
struct node
{
int l,r;
}a[N];
vector vct[];
int t,K,n,m,i,j,k,l,x,y,sa[N],rk[N],Y[N],c[N],len;
char s[N],ans[N];
bool cmp(node a,node b)
{
return a.lb.r-b.l;
return a.lk)
Y[++l]=sa[i]-k;
;i<=m;++i) c[i]=; ;i<=n;++i) c[rk[i]]++; ;i<=m;++i) c[i]+=c[i-]; ;--i) sa[c[rk[Y[i]]]--]=Y[i]; ;i<=n;++i) Y[i]=rk[i]; rk[sa[]]=m=; ;i<=n;++i) rk[sa[i]]=(Y[sa[i]]==Y[sa[i-]]&&(sa[i]+k>n?:Y[sa[i]+k])==(sa[i-]+k>n?:Y[sa[i-]+k])?m:++m);
if(rk[sa[n]]==n)//SA的一个优化
break;
}
rk[n+]=;//注意细节！！
;i<;++i) vct[i].clear(); ;i<=n;i=j) { for(j=i;j<=n&&s[i]==s[j];++j); vct[s[i]-}); } ,j=k=;i>=;--i)
{
l=vct[i].size();
if(!l)
continue;
sort(vct[i].begin(),vct[i].end(),cmp);
;x=l)
continue;
)
{
add(i+);
j=vct[i][x++].r;
}
if(l-x+krk[y])
y=max(j+,vct[i][x].r+);
for(;y<=n;++y)
add(s[y],);
j=n;
break;
}
ans[len+]=;
puts(ans+);
}
;
}