Cursor Distance

题意翻译

给定一个长度为 $n(n\leqslant 10^5)$ 的由小写字母组成的字符串 $s$ 。 当光标在 $x$ 位置时，一次合法的操作定义为选取 $(c,0/1)$ 分别表示一个字符和方向(左/右)，执行该操作会使光标移动到 $x$ 对应方向的 $c$ 字符的最接近的的出现位置(要求必须存在)。 此外定义 $\mathrm{dist(i,j)}$ 为光标初始在 $i$ ，使光标移动到 $j$ 的最小操作次数。 求 $\displaystyle \sum _{i=1}^n \sum _{j=1}^n \mathrm{dist(i,j)}$。

题目描述

There is a string $ s $ of lowercase English letters. A cursor is positioned on one of the characters. The cursor can be moved with the following operation: choose a letter $ c $ and a direction (left or right). The cursor is then moved to the closest occurence of $ c $ in the chosen direction. If there is no letter $ c $ in that direction, the cursor stays in place. For example, if $ s = \mathtt{abaab} $ with the cursor on the second character ( $ \mathtt{aaab} $ ), then: - moving to the closest letter $ \mathtt{a} $ to the left places the cursor on the first character ( $ \mathtt{[a]baab} $ ); - moving to the closest letter $ \mathtt{a} $ to the right places the cursor the third character ( $ \mathtt{ab[a]ab} $ ); - moving to the closest letter $ \mathtt{b} $ to the right places the cursor on the fifth character ( $ \mathtt{abaa} $ ); - any other operation leaves the cursor in place. Let $ \mathrm{dist}(i, j) $ be the smallest number of operations needed to move the cursor from the $ i $ -th character to the $ j $ -th character. Compute $ \displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j) $ .

输入输出格式

输入格式

The only line contains a non-empty string $ s $ of at most $ 10^5 $ lowercase English letters.

输出格式

Print a single integer $ \displaystyle \sum_{i = 1}^n \sum_{j = 1}^n \mathrm{dist}(i, j) $ .

输入输出样例

输入样例 #1

abcde

输出样例 #1

20

输入样例 #2

abacaba

输出样例 #2

58

说明

In the first sample case, $ \mathrm{dist}(i, j) = 0 $ for any pair $ i = j $ , and $ 1 $ for all other pairs.