题目大意

• 给定一个长度为 $n$ 的字符串 $s$，要求给每个字母染色，使得可以通过若干次操作让字符串的字母按字典序升序排列，其中每次操作可以交换两个相邻的不同色的字母。求符合条件的所需颜色总数，并给出构造方案。

• $1\leq n\leq 2\times 10^5$

解题思路

容易发现字典序大的字母若出现在字典序小的字母前面，则为了让字符串的字母按字典序升序排列，必有一步需要将这两个字母进行交换，故这两个字符颜色不能相同。

从前往后处理字符。设已处理的字符中，字符 $c$ 的颜色最大是 $maxn_c$，且即将要处理的这个字符为 $c_0$。考虑已处理的字符中字典序大于 $c_0$ 的字符，为保证该字符的颜色不与它们的颜色相同，不妨令这个字符 $c_0$ 的颜色为

我们只需维护数组 $maxn$，即可在 $\Theta(C)$（$C=26$ 为字符集大小）的时间复杂度内处理一个字母。时间复杂度 $\Theta(nC)$。

AC 代码

#include<bits/stdc++.h>
using namespace std;

int n,maxn['z'+1],ans[200001],color;
string str;

int main(){
    cin>>n>>str;
    for(int i=0;i<n;i++){
        int tmp=1;
        for(int j=str[i]+1;j<='z';j++)
            tmp=max(tmp,maxn[j]+1);
        ans[i]=tmp,maxn[str[i]]=tmp;
        color=max(color,tmp);
    }
    printf("%d\n",color);
    for(int i=0;i<n;i++)
        printf("%d ",ans[i]);
    printf("\n");
    return 0;
}