标签 - 代码源竞赛平台

题目描述

一份记录用小写英文字母标注条目。整理某段记录时，需要把它按原顺序分成若干个非空连续段，每段放入一份档案。每种字母仅能出现在其中一个段里，同一字母在这个段里可以出现多次。

对于一个非空字符串 $T$，记按照上述规则最多能够分成的段数为 $f(T)$。

例如，abac 可以分成 aba、c，所以 $f(\texttt{abac})=2$。对于 abacb，任何满足要求的划分都只能得到一段，所以 $f(\texttt{abacb})=1$。

现有长度为 $n$ 的记录 $S$。请计算 $S$ 的所有非空连续子串 $T$ 的 $f(T)$ 之和。起止位置不同的子串分别计数。

输入格式

第一行包含一个正整数 $n$，为记录的长度。

第二行包含一个长度为 $n$ 的字符串 $S$，为记录中的字母序列，只含小写英文字母。

输出格式

输出一个正整数，表示所有非空连续子串 $T$ 的 $f(T)$ 之和。

样例

5
abacb

24

3
abc

10

数据规模

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$30$	$2000$	无
$2$	$20$	$3 \times 10^5$	A
$3$	$50$		无

特殊性质 A：$S$ 中至多出现两种不同的字母。

对于 $100\%$ 的数据，$1\le n\le 3 \times 10^5$，$S$ 的长度为 $n$，且 $S$ 只含小写英文字母。