双频信号片段

题目背景

深空探测器回传了一段"双频信号"：一串由小写字母组成的序列。科研人员只关心它的连续片段是否"稳定"。

题目描述

给定一个长度为 $n$ 的字符串 $s$（下标从 $1$ 开始）。

对任意连续片段 $[l, r]$，称它是不稳定的，当且仅当 $s_l$ 在片段 $[l, r]$ 中恰好出现一次，或 $s_r$ 在片段 $[l, r]$ 中恰好出现一次。否则（即 $s_l$ 与 $s_r$ 在片段中都至少出现两次），称片段是稳定的。

求字符串 $s$ 中"不稳定"的连续片段数量。

输入格式

一行一个字符串 $s$，仅由小写字母组成。

输出格式

一行一个整数，表示不稳定片段的数量。

【样例 1】

【样例 1 输入】

ab

【样例 1 输出】

3

【样例 1 解释】

三个片段 $[1,1]$、$[2,2]$、$[1,2]$ 的端点字符都只出现一次，均不稳定。

---

【样例 2】

【样例 2 输入】

aa

【样例 2 输出】

2

【样例 2 解释】

$[1,1]$、$[2,2]$ 不稳定；$[1,2]$ 中 $a$ 出现两次，稳定。

---

【样例 3】

【样例 3 输入】

aba

【样例 3 输出】

5

【样例 3 解释】

$[1,3]$ 中首、尾的 $a$ 均出现两次，稳定；其余 $5$ 个片段不稳定。

---

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足 $n \le 10$。

---

【样例 5】

见选手目录下的 Data/sample5.in 和 Data/sample5.ans。

该样例满足字符串只由一种字符组成。

---

【样例 6】

见选手目录下的 Data/sample6.in 和 Data/sample6.ans。

该样例满足 $n \le 1000$。

---

【样例 7】

见选手目录下的 Data/sample7.in 和 Data/sample7.ans。

该样例满足 $n \le 10^5$。

---

【数据规模与约定】

对于全部数据，$1 \le n \le 3 \times 10^5$。

测试点编号	分数	特殊性质
1 ~ 2	5	$n \le 10$
3 ~ 4		字符串只由一种字符组成
5 ~ 6	20	$n \le 1000$
7 ~ 8	30	$n \le 100000$，字符串仅由 a、b 组成
9 ~ 10	40	$n \le 300000$

---

【大样例下载链接】

点击下载本题选手目录