http://m3.codeforces.com/contest/1296/problem/E2

タイトルはあなたに小文字で構成されたシーケンスをあげるということです.
今あなたはすべての文字に色をつけることができて、同じアルファベットが多種の色があることに注意して、しかしさっき1言ったのは文字で、つまりiはすべての位置は1種の色だけあって、今、あなたは1つの能力があって異なる色の文字を交換することができて、あなたに何種類の色が元のシーケンスをシーケンスに変えることができることを聞くことができます;
色種数を出力し、スキームを出力します.
考え方:
私たちは1つの文字が彼の前の彼より大きい文字と交換しなければならないことを発見することができて、私たちはこれらの彼より大きい文字を集合sと総称して、それでは私たちのこの文字の色が彼らと違っていなければならなくて、それでは色はきっと集合の中で最も小さいものを選んで現れたことがなくて、mexが知っているでしょう.たとえば集合の色が2,4,5である場合,そのときの色は必ず1である.では、私たちはすべてのアルファベットの検索セットを維持します.つまり、文字列を最初から遍歴し、現在文字列がidであることに遭遇しました.私たちはその文字の所属と検索セットに入り、父を見つけ始めました.この新しい文字は父の色(x)+1です.次に、idより小さい文字の色(x、つまり左のxと同じ色)を現在のx+1に集計します.だから後ろのidより小さい文字はidの色+1しかできません.

#include
#define MAXN 200005
using namespace std;
int n,vis[26][MAXN],pre[26][MAXN],ans[MAXN];
char s[MAXN];
inline int find(int id,int x)
{
	return x == pre[id][x] ? x : pre[id][x] = find(id,pre[id][x]);
}
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i = 0;i < 26;++i)
	{
		for(int j = 0;j <= n;++j)
			pre[i][j] = j;
	}
	int mx = 1;
	for(int i = 1;i <= n;++i)
	{
		int id = s[i] - 'a';
		ans[i] = find(id,0)+1;
		mx = max(mx,ans[i]);
		for(int j = 0;j < id;++j)
		{
			if(!vis[j][ans[i]])
			{
				vis[j][ans[i]] = 1;
				pre[j][ans[i]-1] = ans[i];
			}
		}
	}
	printf("%d
",mx);
	for(int i = 1;i <= n;++i)
		printf("%d ",ans[i]);
	return 0;
}